平面图顶点着色问题的极大独立集的构造

⊂可在www.sciencedirect.com在线获取理论计算机科学电子笔记354（2020）75-89www.elsevier.com/locate/entcs平面图顶点着色问题的极大独立集的构造克里斯蒂娜Lopez-Ram'ıreza，1，2，JorgeEduardoGuti'errezGomeza，1，3和Guillermo De Ita Lunaa，1，4aBenem'eritaUniversidadAu t'onomadePuebla14SurEsq. SN. 克劳迪奥，加州大学 -Edif CCO1，Puebla，Pue.，M'exico摘要我们分析了平面图的顶点着色问题，并提出将经典轮和多面体轮作为平面图的基本模式。我们分析了轮间组合的可着色性，并提出了一种基于三条规则的顶点着色算法。这些规则是：1）选择边界中的顶点2）加工包容轮。3）加工中心剩下的车轮我们的方法形成了一个极大的独立集S1V（G）的车轮因此，我们证明了如果图G′=（G-S1）是3-可着色的，则这意味着G存在一个有效的4-可着色.关键词：平面图，顶点着色，轮图，多面体轮图，极大独立集。1引言通过图G的一个真染色（或仅仅是一个染色），我们称之为一个赋值 一个颜色（集合的元素）到G的顶点，每个顶点一种颜色，使得相邻的顶点被不同地着色。G的任意着色中的最小颜色数称为G的色数，记为χ（G）.当G可以从k个颜色中着色时，称G是k-可着色的，而这种着色称为k-着色.若χ（G）=k，则称G是k-染色的，且每一个k-染色都是G的最小染色.1感谢SNI-CONACYT为这项工作提供的经济支持。2电子邮件：cristyna2001@hotmail.com3电子邮件：用户名ed@hotmail.com4电子邮件：deita@cs.buap.mxhttps://doi.org/10.1016/j.entcs.2020.10.0071571-0661/© 2020作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。76C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75⊂⊂色数χ（G）的计算是多项式可计算的，如果G是k-可着色的，且k≤2;否则，该问题成为NP-完全问题[6]。因此，有许多与图的着色有关的未回答的问题。图顶点着色问题是一个活跃的研究领域，在频率分配，规划，计算机视觉，调度，图像处理等领域有许多有趣的子问题和应用[4，9]。在这种背景下，平面图在图论领域和复杂性理论中起事实上，平面图有几个有趣的性质，因为它们是4-着色的，分散的，并且它们的内部结构被优雅而简洁地描述[3]。在顶点着色问题的情况下，2-可着色性在多项式时间内是可解的。对于一些图的拓扑结构，如AT-自由图和完美图，3-可着色性也在多项式时间内得到了解决。此外，还成功地解决了几类图，如可比图、弦图和区间图的χ（G在所有这些情况下，特殊的结构（模式）已被发现，以表征类的图是着色的多项式时间复杂度。在这篇文章中，我们介绍了我们认为是形成任何平面图的基本图形模式，我们称之为多面体轮。考虑了多面体轮之间的组合，分析了其色数。我们提出了一种新的方法来识别经典和多面体车轮的可着色性2预赛设G=（V，E）是一个无向简单图（即有限无环无重边图），其顶点集为V（或V（G）），边集为E（或E（G））.我们假设读者熟悉有关图论和平面图的标准术语和符号，参见例如[10]图论中的标准概念。我们在这里只提出一些我们将使用的符号如果有一条边{v，w}∈E连接两个不同的顶点，那么我们说v和w是相邻的。x∈V的邻域是N（x）={y∈V：{x，y} ∈E}，其闭邻域用N[x]表示，是N（x）<${x}。集合A的基数表示为：|一|. 顶点x∈V的度为|N（x）|，它会的用δ（x）表示。一个图，其中每对不同的顶点是相邻的称为完全图。n个顶点的完全图记为Kn。我们称GJ=（VJ，EJ）是G=（V，E）的一个子图，如果VJV和JE. 若VJ=V，则称GJ为G的一个生成子图.如果GJ包含G中连接VJ中两个顶点的所有边，则称GJ是由VJ诱导的。这样，G−VJ就是V−VJ的导出子图。类似地，如果EJ<$E，则G−EJ=（V，E−EJ）。如果VJ={v}且e={u，v}，则该记法分别简化为G−v和G−e。给定一个图G =（V，E），S∈V是G中的一个独立集，如果对S中的任意两个顶点v1，v2，{v1，v2}∈/E. 设I（G）是G的所有独立集的集合.C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7577一个独立集S∈I（G）是极大的，简称MIS，如果它不是任何更大的独立集的子集。此外，如果它在I（G）中的所有独立集中具有最大的尺寸，则它是最大的2.1平面图图G的一个图Γ将每个顶点v映射到平面的一个不同点Γ（v），将每个边{u，v}映射到一条简单的开Jordan曲线Γ（u，v），端点为Γ（u）和Γ（v）。一个图形是平面的，如果它可以嵌入（或它有一个嵌入）在空间中的方式，没有两个边缘相交，除了在一个共同的端点。一个图G是平面的，如果G在平面中有嵌入。平面图形将平面划分为称为面的连接区域。无界面通常称为外表面或外部面。一般来说，一个平面图在平面上有很多嵌入。平面图的两个嵌入是等价的，当一个嵌入中的一个面的边界总是对应于另一个面的边界时。平面嵌入是平面图的等价类，并且通过与每个顶点关联的边的顺时针圆形顺序来描述。一个极大平面图是一个没有边可以添加到没有失去平面性。因此，在n≥3的极大平面图G的任意嵌入中，G的每个面的边界都是三角形。最著名的结果之一是Kuratowski该定理给出了判定一个图是平面图的一个判据。Kuratowski证明，如果一个图不包含是K5或K3，3的子图，其中K5是5阶完全图，K3，3是在每个划分集中有3个顶点的完全二部图，则该图是平面图。类似地，Wagner[13]的定理指出，图G是平面的当且仅当它没有K5或K3，3作为子图。然而，这两个特征是不同的，因为一个图可以承认K5作为小的，而没有一个子图是K5的细分。著名的四色定理（4CT）说，每个平面图是顶点4-可着色的。Robertson等人[11]描述了一个O（n2）4-着色算法。这似乎很难改进，因为它可能需要4CT的新证明。另一方面，决定一个平面图是否只需要三种颜色是一个NP-困难问题[6]。然而，Grüotzch定理[ 5 ]证明了每个无三角形平面图都是3-可因此，平面图着色的难点在于判定一个无限制平面图是3-可着色的还是4-可着色的。并不是所有的图都是平面的。然而，平面图在现实世界的应用中非常自然地出现，例如公路或铁路地图，电子印刷电路，化学分子等。平面图在这些问题中起着重要作用，部分原因是一些实际问题可以有效地解决平面图，即使它们对于一般图来说是难以解决的[10]。近年来，平面图引起了计算机科学家78C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75一1小时4我235BC67D8J10119e1412 f13 15G12HC345我67 8 9J10 11DFe121314153平面图在本节中，我们将介绍我们开发的用于算法提案的概念。平面图G具有一组闭非连通区域F（G）={f1，.，f k}称为面孔。每个面fi∈F（G）由界定其内部区域的边的集合表示。G中的所有边{u，v}，如果不是G的任何面的边界，则称为非循环边。两个面fi，fj∈F（G）是相邻的，如果它们至少有一条公共边，这是（E（fi）<$E（fj））<$。否则，他们是一个小脸。请注意，独立的面可以有公共顶点，但它们没有公共边。一组面是独立的，如果每一对面都是独立的。一条非循环边与一个面相邻，如果它们只有一个公共顶点。如果两条非循环边共享 一个 公 共端 点 ，则 它 们 是相 邻 的。 我 们从 G 建 立一 个 内面 图Gf= （X ，E（Gf）），如下所示：(i) 每个面fi都有一个顶点x∈X。(ii) G的每一条非循环边都与Gf的一个顶点相连，并与G f的顶点标号相同。(iii) 存在连接Gf的两个相邻顶点的边{u，v}∈E（Gf），当其对应的面（或非循环边）在G中相邻时.Gf是平面图G的内面图。我们必须强调，G f不是G的对偶图，因为在G f的构造中，G的外表面不被考虑。请注意，Gf也是一个平面图，其顶点表示G的面或边（如图1b所示）。 图G的内面图Gf提供了图G的面之间关系的一个映射，它对于寻找3-着色模式图是有用的.对于任意平面图G=（V，E），我们将G的与其外表面相关联的顶点集记为Ext（G）。同时，G的内部顶点，用Int（G）表示，是不与外面相关联的顶点。即Int（G）=V（G）−Ext（G）。(a) 图G具有可识别的面（b）图（1a）中的内面图Fig. 1. 一个平面图及其内面图C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75793.1经典和多面体车轮平面图中的一个基本模式是经典轮rxrG，其中rG表示G中所有轮的集合。 单个轮rx由顶点Crx形成。 C rx 被称为车轮的中心顶点。Crx与所有围绕它形成一个环的顶点相邻。每个面（称为轮轴）是一个三角形。轮中有两类顶点：中心顶点和形成环的顶点。注意，平面图G的轮在其内面Gf中被表示为圈。偶数轮（奇数轮）有偶数（奇数）个面。 所有具有多个偶数三角形的轮子都是3色的。同时，任何含有K4或奇轮的平面图都需要四种颜色，以便正确地给这些图着色。然而，这些拓扑不是唯一的4-可着色的情况。例如，在图1a中，一个简单的轮子由边b-c-e-f-d组成，其中心顶点是j。这个轮子的轮轴都是三角形的。同时，在图1b中，示出了来自图1a中的曲线图的内部面曲线图Gf我们扩展类的车轮考虑任何多边形作为一个轴面的车轮。这种类型的轮被称为多面体轮。这意味着在rx的环中有一些顶点围绕中心顶点Crx，并且不与中心相邻。 中心顶点是多面体轮的所有轴面的公共关联顶点，平面图G的多面体轮在其内面图Gf中表示为一个圈.我们将多面体轮中的环顶点划分为轴顶点，如果它们与中心顶点相邻。否则，它们被认为是额外的轴。在多面体轮中的边的情况下，我们有循环的边和与中心关联的边，称为轮辐边。4染色平面图它是容易的（在线性时间上的图的大小），以认识到，如果一个输入图是2-可着色的，因为它只涉及图中偶数圈的识别。类似地，Grotszch定理[ 5 ]证明然而，平面图的3-着色的识别是一个经典的NP完全问题[6]。当一个平面图中包含三角形时，要区分它的三个着色和四个着色是很困难的，因为没有（至少到目前为止）一个充分的条件来区分一个平面图的3-着色。设Three={ 1， 2， 3}为包含三种不同颜色的集合。我们表示函数Color（v），它为顶点v分配一个唯一的颜色。设v是G的一个顶点，其颜色c∈ {1， 2， 3， 4}，Tabu（v）∈ {1， 2， 3， 4}是与v相关联的禁止颜色。事实上，Tabu（v）包含了与N（v）中的顶点相关联的颜色。 当T abu（x） =0时，x是一个自由顶点. 一个集合A是标记的，当x∈A;Tabu（x）={1}，在这种情况下，我们说每个顶点x∈A都不是自由的。在这一节中，我们开始介绍简单的算法和结果，从我们得到的，以分析之间的3或4着色的基本图形模式80C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75由图表的轮子组成。我们开始考虑一个算法着色简单的车轮。我们介绍了一个典型的车轮着色，其中心顶点被分配的第一个颜色。颜色2、3被交替地分配到循环的顶点。此着色从轮盘的任何三角形面开始，并从循环的顶点沿逆时针方向进行。仅当访问循环的最后一个顶点时，才确定是否需要第四种颜色引理4.1中心点独立的偶数简单轮的并是3-可着色的.证据当轮子的所有中心顶点在图上形成一个独立的集合时，第一个颜色可以分配给这些顶点。车轮之间的公共边缘如果图的中心顶点被移除，因为它们已经被着色，剩下的子图是二分的，因为它只有圈的边。由于子图中只剩下偶数圈，则子图是2-可着色的。利用中心点与圈顶点的不同颜色，得到了这类平面图的3-染色。Q我们将把一个无环图看作一棵树。在树的情况下，我们调用节点到树的每个顶点。已知无圈图是2-可着色的。然而，考虑到无圈图的任何顶点都限制了三个颜色中的任何一个颜色，则无圈图是3-可着色的。引理4.2一个非循环分支是3-可着色的，如果它的所有顶点最多有3种颜色作为限制。证据非循环分支被认为是一棵以vrV（rx）为根的树。从vr开始进行预序着色，其中Color（vr）=MIN{T hree−T abu（vr）}。如果我们按照每个要着色的新级别的预先顺序前进，则新级别中的所有节点y将最多具有来自其父节点的两种受限颜色和一种可能存在于Tabu（y）中的颜色。因此，一个颜色一直是可用的三个可能从三个。当树的所有节点都被预先访问过之后，我们的方案已经对所有节点着色。 Q当Gf是一棵树时，我们说G（它对应的平面图）是一棵多边形树[8]。这意味着，虽然G有圈，但所有这些圈都可以排列成一棵树，其节点是多边形而不是G的单个顶点。下面的定理表明，从平面图中确定访问所有面的顺序，就足以得到多边形树的3-着色的一个有效过程。定理4.3若平面图G的内面图具有树拓扑，则G是3-可着色的。证据 设Gf是平面图G的内面图。因为任何一张G是单圈，则它是3-可着色的。G的所有非循环边也是3-可染的，C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7581因为所有的非循环图都是2-可着色的。G的3-着色过程可以通过按预序遍历Gf的节点来首先着色Gf的父节点的面，然后着色其子节点的面。在每个当前级别中，考虑两个相邻的面（G中的父亲和孩子）。两个区域在其公共边界中具有两个公共极值顶点x、y这些公共顶点首先被着色，然后，两个面中的其余顶点最多有两种禁止的颜色。请注意，在两个面中的任何一个中都没有一对相邻的顶点u和v，使得{u，v}<$（N（x）<$N（y））。这是因为{x，y，u，v}形成K4，而这个子图不能是任何多边形树的一部分。因此，对于两个面中的所有剩余顶点，在“三个”中的三种可能颜色中至少有一种颜色可用。当树Gf的所有节点都已按前序访问时，3-着色过程结束。 Q如果一个平面图G没有多边形树拓扑，这意味着Gf中有圈，因此G中有轮。对于这类平面图，有可能识别3-着色图形模式。引理4.4所有的多面体轮都是3-可着色的。证据如果rx是一个多面体轮，那么有一个轴面不是三角形。因此，V（rx）中至少有一个顶点ve不与轮的中心顶点vx相邻;否则，所有轴面都将是三角形。 图R−ve =（rx−v e）是一棵多边形树;因此，根据引理4.2和定理4.3，它是3-可着色的。如果ve与vx具有相同的颜色，则R−ve的任何典型的3-染色都可以扩展为rx的3-染色，因为在典型的染色中，中心顶点的颜色不用于循环的顶点。因此，中心Q几个作品都集中在识别基于周期的长度的3-着色模式。例如，Borodin et.等人[1，2]证明了距离小于4且无5-圈的无三角形平面图的3-可染性。类似地，对于没有长度为4到7的圈的图。另一方面，我们对平面图中的3-可着色拓扑和4-可着色拓扑进行了区别分析。本文主要研究多面体轮并所形成的拓扑结构的识别，并设计了一个着色算法。3-可着色多面体轮的并集不一定是3-可着色的。例如，在图2a中，如果我们将每个公共面视为包含它的多面体轮的面之一，那么我们将每个多面体轮视为独立于其他多面体轮，并且在这种情况下，每个轮都是3-着色的引理4.4. 然而，最终图（车轮的并集）必须要求四种颜色，正如我们使用变量x，y，z来表示要使用的3种不同颜色。请注意，带有标签“？”不能用x、y、z表示的颜色着色，因此，该图请求第四种颜色。82C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75zyzXXyzy？yze2e3zyzXXyzy？yze1(a) 不可3着色(b) 用{e1，e2，e3}构建光盘图二、一个平面图G，以及一个包围G的三点圆盘5着色算法设G是输入平面图的一个嵌入，Gf是其对应的内面图.设rx是一个以Crx为顶点的多面体轮.设Exc（rx）=Cycle（rx）<$Ext（G）是rx的与G的外表面相关联的圈的顶点的集合由于多面体轮是我们的着色算法要识别和处理的基本模式，所以我们使用特殊的结构来表示和编码图G的轮的性质。例如，对于任何车轮每次计算并更新rx∈G;Crx、Cycle（rx）、Exc（rx）、Inc（rx），从而更新输入图G。因此，必须使用特殊的计算结构来高效地更新G中每个轮的关联结构。定义5.1给定两个多面体轮rx和ry，其顶点中心分别为Crx和Cry，如果Cycle（ry）<$V（rx）成立，则我们说ry被rx包含。当一个轮r y被一个轮r x所包含，并且当r x/= r y时，则存在一个vertxu∈Cycle（rx），使得u∈/V（ry）。 如果一个颜色被分配给C rx，suchasColor（C rx）= 1，那么轮子r x被简化为一个面f x，它将成为轮子r y的一个面。让我们用rx，y表示由rx在fx面上熔合形成的新轮，fx面现在也是轮ry的一部分。面fx在rx，y中不是三角形，因为至少顶点u∈V（fx）不与Cry相邻。因此，多面体轮r x，y是3-着色的引理4.4。注意，在融合轮r x，y上，顶点对{C ry，u}可以具有相同的颜色，例如Color（C ry）= Color（u）= 2，并且所得到的子图（r x，y−{C ry，u}）现在是具有一种受限颜色的非循环分量，并且因此根据引理4.2是3-可着色的。我们可以说，顶点x是从当前图G中被确定地移除的，当x已经通过使G=（G− {x}）而被赋予颜色时最后，C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7583x调整图的参数δ（y）=δ（y）−1，y∈N（x），Ext（G），Int（G），以及与图的轮相关联的参数我们的算法的停止条件将在每一步之后进行检查。停止条件如下。i) 如果生成的图GJ是一棵多边形树，则在GJ上建立一个3-着色根据定理4.3。ii) 如果生成的图GJ不含三角面，则GJ是3-可着色的.iii) 如果GJ是无圈的，则建立GJ的3-着色（基于引理4.2）。现在，我们提出我们的一般着色算法。算法1.步骤1：选择外部顶点以指定颜色1。给定一个图G，确定一个自由顶点e∈Ext（G），它可以是Gf中最大数目的面的一部分。然后，指定Color（e）= 1，并且y∈N（e）; Tabu（y）={1}。然后，从G中移除顶点e，更新G和Ext（G）。外部顶点的选择和消除是一个迭代过程，直到Ext（G）中没有更多的自由顶点。我们检查结果图是否至少符合一个停止条件。否则，我们继续下一步。步骤2：加工包容轮和多面体轮。(i) 处理所有包含的车轮：给定一对轮子rx，ry，如果（Cycle（ry）<$V（rx）），则Color（Crx）= 1。在这一步中，我们处理当前图上所有包含的轮(ii) 中心列表Sc = { C r 1，.，Crk}由图G中所有轮的中心点构成。Sc排序首先考虑经典轮的中心，然后考虑多面体轮的中心在每个分区内，首先考虑奇数轮，然后考虑偶数轮的中心在每个分区中，排序遵循以下规则：min{|N（C rx）S c|}，对于类似的值，规则max{|Exc（r x）|}已应用。然后，通过首先选择一个自由顶点Cri∈Sc来应用迭代过程，以分配Color（Cri）= 1，Sc=Sc−{Cri}，然后标记N（Cri）。算法结束在轮ry被另一个rx包含的情况下，步骤（2a）保证rx的中心被分配颜色1而不是ry的中心。此外，步骤2保证在所得到的图中，不存在任何经典轮，并且颜色为1的顶点形成极大独立集S1<$V（G）。例5.2在下面的例子中，我们展示了我们的建议的步骤顺序的相关性。为此，让我们考虑图3a中所示的曲线图。算法的第一步是处理外部顶点。在这种情况下，选择g84C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75JG一XDBCeF一XDBCeF要被分配颜色1，c（g）=1，因为g与外部顶点集合上的最大数量的面关联。图3b显示了生成的图GJ=G− {g}。 注意每个顶点u ∈ Ext（G）都有Tabu（u）={1}。对于GJ，识别循环：循环（x）={a，b，d，c}，循环（d）={x，b，c}。G中有两个经典轮，其中心为x和d。这些轮子可以容纳：rdrx和rd/rx。当我们应用包含轮规则-步骤（2a）时，我们被迫处理中心为x的轮，如图3c所示。然而，如果应用步骤（2b），而不是步骤（2a），将颜色1分配给中心d，则得到的图如图3d所示。请注意，在图3d的结果图中，顶点a，x，b和c形成了众所周知的图K4，已知它是4-可着色的。由于颜色1在第一步之后使用，因此该颜色不能用于着色K4，因此图3d中的图变为5-可着色。然而，考虑到我们算法中步骤的实际顺序，图3c中的结果图是3-可着色的，因此，输入图是4-可着色的。(a) 输入图G(b) 无顶点g的图G一DBCeF一XBCeF(c) 无{g，x}的图G（d）无{g，x，d}的图G图3.第三章。为（3a）中的输入图构建4-着色我们的算法的步骤1由以下引理支持C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7585J引理5.3每个平面图G都有一个4-染色，使得第一个颜色不分配给Ext（G）的顶点。证据设G是一个平面图。G可以被由3个顶点{e1，e2，e3}通过边{{e1，e2}，{e1，e3}，{e2，e3}}连接形成的圆盘D包围。D是以如下方式绘制的。首先，在图G的外表面上画出顶点e1，并画出边：{e，e1}，e∈Ext（G）.因此，只有一个入射到G的外表面的边{u，v}将保持为入射到（G∈{e1}）的外表面然后，在（G<${e1}）的外面和{u，v}的前面画e2和e3，这样我们就可以添加新的边{e2，u}和{e3，v}，它们既不与（G<${e1}）中的任何边相交，也不与G的原始边相交。最后，我们添加边{{e1，e2}，{e1，e3}，{e2，e3}}以形成圆盘D。注意，以这种方式，已经构建了新的平面图GJ，其中Ext（GJ）={e1，e2，e3}。因此，由于4CT定理，GJ存在一个4-着色每当我们选择颜色而不失去其一般性，例如， 颜色1被分配给e1（Color（e1）=1），则顶点{e2，e3}Ext（G）保持非自由，其Tabu集包含颜色1。当我们从G中移除e1时，则建立一个新的平面图G1=GJ−{e1}，其中颜色1不能分配给Ext（G1）中的顶点。因此，G1中的任何4-着色都将是G的4-着色，其中第一个颜色不被Ext（G）的顶点使用Q图3a中示出了由包围整个图的三个边缘形成的圆盘的示例。圆盘由边缘{{g，e}，{g，f}，{e，f}}形成。注意Ext（G）={g，e，f}在（G−Ext（G））中包含另一层外部顶点，表示为Ext（G1）={a，b，c}。当Color（g）= 1时，Ext（G）和Ext（G1）中的所有剩余顶点都被标记。 因此，Ext（G1）中没有顶点具有颜色1，正如前面的引理所宣称的那样。当一个顶点e∈Ext（G）着色时，则它从G中完全去除.因此，NG（e）中的顶点是非自由的。注意，当e被移除时，NG（e）中的顶点现在是Ext（G− {e}）的一部分图2b中示出了由包围整个图形的三个边缘形成的盘D的另一示例，由{e1，e2，e3}形成的盘包围图2a的图形。注意，我们的建议的步骤1是由引理5.3证明的，因为我们总是可以构建任何平面图G的4-着色，其中颜色1不用于Ext（G）。因此，我们可以开始将颜色1分配给G的最大数量的外部顶点，然后移除它们以形成新的平面图GJ，直到e∈Ext（GJ）;Tabu（e）={1}。在所得到的平面图GJ中，它的内部顶点是自由的，外部顶点是标记的。作为引理5.3的逻辑结果，在GJ上保证4-着色，其中颜色1从Ext（GJ）中排除。这个4-着色被扩展到G的4-着色，其中颜色1被分配给最初从Ext（G）中的原始集合中移除的顶点，因为这些顶点不会有任何颜色为1的相邻顶点，因为Ext（GJ）排除了颜色1第1步是我们方法中唯一一个由4CT定理证明的步骤86C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75另一方面，在我们的建议中包含步骤1是合理的，因为它加快了4-着色的构建步骤2从G中移除任何包含轮和经典轮，在G中仅保留中心顶点自由的多面体轮。这使得G中的中心顶点自由在这个意义上，步骤2使剩余的图不受K4的影响.定理5.4在结果图中没有任何剩余的经典轮Gr在应用步骤2之后。证据矛盾。设Gr是应用步骤2后的剩余图，并假设存在一个以 Crx为中心的轮rx∈Gr，其中每个面都是三角形。如果Tabu（Crx）=1，则步骤2指定Color（Crx）= 1，并且rx被减少到一个面fx。 另一方面，Tabu（Crx）={1}仅在车轮以Cry为中心处理r y，使得Crx∈N（Cry），并且其中Cycle（Cry）嵌入在rx的一个三角形面中。这意味着rx包含在fa∈F（rx）中;否则，Cycle（ry）将穿过rx的辐边。如果Cycle（ry）嵌入在E（fa）中，那么我们将有以下条件：(i) N[C ry]<$N [C rx]。 在这种情况下，Crx应该在我们算法的 Cryy准则（2a）之前被分配颜色1。因此，Crx∈/N（Cry）。(ii) |为|Exc（r x）|=2。|= 2.以来|Ext（G r）|≥ 3且Ext（G r）只有3次或更大的顶点，则应该存在另一个以Crz为中心的轮r z，|Exc（r z）|>>|Exc（r x）|和|Exc（r z）|>>|Exc（r y）|并且其中（Cycle（rz）<$Cycle（ry）<$Cycle（rx））<$。当Color（Crz）=1时，Rz被简化为具有严格大于3的长度的新面Fz这个新面是轮rx和ry的一部分;因此，rx应该具有至少一个非三角形面。Q定理5.4包含了K4和任何其它经典轮在所得图GJ中的禁止存在性。如果GJ是一棵多边形树，则建立一个3-着色。另外，还可以提出不同的算法来构造G-J的3-着色.例5.5图1a显示了平面图G，它必须在 这个例子。算法的第一步是考虑外部顶点：Ext（G）={a，b，g}被分配颜色1。按照步骤1的规则，并使用G的内面图（图1b），选择顶点x∈Ext（G）。在这种情况下，选择顶点g进行着色：Color（g）=1，因为g具有Ext（G）中的最大程度。接下来，顶点N（g）用颜色1标记。然后从图G中移除g，G=（G− {g}）。由于没有另一个自由的外部顶点，我们继续步骤2。作为第二步的第一部分，处理附属于其他车轮的车轮生成轮的列表rh={a，b，i，c}，ri={h，b，c}，rj={b，d，f，e，c}。 我们可以看到轮rh包含轮ri，因此顶点h被选择着色。颜色（h）= 1，N（h）标记为1。因为C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7587一B一我BCDCeF一BC一HB我CDJeFG如果没有更多的包含轮，则我们进行到步骤（2b）。将创建所有自由三角轮中心的列表。在这种情况下，列表由顶点j组成;因此，这个顶点是着色的。颜色（j）= 1。此外，j从图G=（G−{j}）中移除，并且其邻域标记为1。此时，图中的所有顶点在其Tabu集中的颜色为1，（Tabu（V（G））= 1）。图4中显示了结果图，图5中显示了其对应的内面图。我们可以看到它是一棵多边形树，因此根据停止条件（i），基于定理4.3建立了G上的一个3-染色。见图4。移除颜色为1的顶点后的G图五.图中图的内面图Gf。4在GJ是3色的之后，我们返回在步骤1和2中用颜色 1结果图G是一个4-着色图（图6中显示了4-着色）。见图6。 G的A 4-着色5.1算法设G =（V，E）是一个输入平面图，n = |V|和m = |E|.在算法的第一部分，我们选择一些外部顶点并将其删除。这个过程会迭代，直到当前图中没有更多的外部自由顶点。在最坏的情况下，图将是外平面的（所有顶点都在外部面），我们可以选择其中任何一个，复杂度为O（n）。88C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）75在我们的算法的步骤（2a）中，通过使用存储车轮的组件的特殊数据结构来搜索和处理所包含的车轮。我们必须使用具有O（m）时间复杂度的广度优先搜索过程来构建车轮的每个周期之后，我们比较每个车轮的一个周期与其余车轮的每个其他周期，在最坏的情况下进行最多n2次比较在这一步中，每个圈都被形成为一串顶点，这些顶点应该与G中的所有其他圈进行比较。时间复杂度为O（n）。在步骤（2b）中，我们必须基于三个标准对当前图的所有轮进行排序;第一，轮的奇偶性，第二，基于规则min{|N（C rx）S c|}和max{|Exc（r x）|}中。因此，我们使用一个典型的排序算法对列表进行排序，该算法的复杂度为O（n·log（n））。总的来说，由于三个主要步骤是顺序的，我们可以通过取所有步骤中最大的复杂度来计算算法的一般复杂度：O（max{O（step1），O（step2），O（step3）}）=O（n2）6结论我们确定经典轮和多面体轮是平面图形成的基本模式之后，我们分析了这些轮和它们的组成，以从输入平面图G构造一个极大独立集（MIS）。G的MISM是由一个算法建立的，该算法基于三个规则。第一个规则是考虑指定颜色1的非相邻外部顶点的最大数量稍后，将选择从属于其他车轮的车轮中心。最后，根据当前图中每个中心顶点的经典、多面体、偶数、奇数和最小内连通的顺序，最后，我们证明了如果图GJ=（G-M）是3-可着色的，则G是4-可着色的。这里提出的过程可以用来开发一个强大的算法着色平面图。在我们未来的工作中，我们正在考虑扩展我们的建议，开发一个通用的平面图着色算法引用[1] Borodin和A.拉斯波特A sufficient condition for planar graphs to be 3-colorable，Journal ofCombinatorial Theory，Series B，88（1977），pp.2003年17日至27日[2] O.V. Borodin，A. N. Glebov和A. Raspaud和M.R.愿你平安没有长度为4到7的圈的平面图是3-可着色的，Jour。 组合理论，系列B，93，pp。303-[3] P. Cortese和M.帕特里尼亚尼平面性测试和嵌入。Press LLC，2004.[4] Z. D vora'k，D. Kr′al和R. 托马斯曲面上的三色无三角形图。 P roc。 20thACM-SIAM Symp.离散算法，pp。120-[5] H. Gr？otz c h. EinDreifar benforcefurdreikreisfreieNetzeaufderKugel. 聪明Z. 马丁-路德-哈雷-维滕贝格数学大学自然。Reihe 8，pp. 109[6] D.约翰逊NP完全性专栏：持续指南。Jour. Of Algorithms 6，pp.434-451，1985.C. López-Ramírez et al. /Electronic Notes in Theoretical Computer Science 354（2020）7589[7] K.库拉托斯基关于拓扑学中的断层问题。基金数学，第15卷，第271 - 283页，1930年。[8] C. 我来了，G。 DeIta和A. 奈里通过增量满足性实现多项式树的3-着色。LNCS的模式识别，卷10880，pp。93[9] G. B. Mertzios和P.G.斯匹拉基斯小直径图3-可染性的算法和几乎紧结果。技术报告。arxiv.org/pdf/1202.4665v2.pdf，2012年。[10] T. Nishizeki和N.千叶平面图：理论与算法。Elsevier，第32卷，pp. 83[11] N.罗伯逊，D.P.桑德斯，P.D. Seymour和R.托马斯四色定理。组合论杂志。 第70卷，pp. 2-44，1997年。[12] J·斯塔乔3-在多项式时间内对无AT图着色。In：Cheong，O.，Chwa，K.-是的，帕克，K. （合编）。算法和计算，ISAAC 2010。LNCS，卷6507，pp. 144-155. Springer，Heidelberg，URL：https://doi.org/10.1007/978-3-642-17514-513，2010.[13] K. 瓦格纳 UübereineEigens chaftdere benenKomplexe. MathematischeAnnalen，volecule114，pp. 570-590，1937年。