平面图着色中的启发式算法

−可在www.sciencedirect.com在线获取理论计算机科学电子笔记354（2020）91-105www.elsevier.com/locate/entcs平面图着色的一个启发式算法GuillermoDeItaLuna a，1，CristinaL 'o pez-Ram'ırez a，2，AnaE. DeIta-Varela a，3和JorgeE. Guti'errez-G'omeza，4aBenem'eritaUniversidadAu t'onomadePuebla14SurEsq. SN. 克劳迪奥，加州大学 -Edif CCO1，Puebla，Pue.，M'exico摘要本文提出了一种基于输入图的极大独立集S的平面图着色算法。最大独立集S必须满足某些特征。例如，S包含出现在G的最大奇数圈数中的顶点。 建设的S考虑输入图G的内面图，以选择属于G的最大数量的奇面的每个顶点。在输入平面图G的内面图Gf上的预序遍历为我们提供了一个的临界区域的部分极大独立集的构造策略。 因此，这些部分极大独立集的并集形成G的极大独立集S。这允许我们首先对图（G S）中对分解G至关重要的顶点进行着色，图（G S）是多边形树，因此是3-可着色的。关键词：3-着色图，极大独立集，平面图，独立路。1引言图的顶点着色问题是用尽可能少的颜色给图的顶点着色，使得相邻的两个顶点不能得到相同的颜色。如果存在这样的k色着色，则该图是k-可着色的。图G的色数记为χ（G），表示G的正常染色所需的最少颜色数. k-可染性问题是指判定一个输入图G是否是k-可染的.固有的计算复杂性，与解决NP-hard prob- lems，激发了寻找替代方法，它允许在多项式时间的解决方案的特殊情况下的NP-hard问题。比如在1电子邮件：deita@cs.buap.mx2电子邮件：cristyna2001@hotmail.com3电子邮件：aeda 5e@hotmail.com4电子邮件：用户name@hotmail.comhttps://doi.org/10.1016/j.entcs.2020.10.0081571-0661/© 2020作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。92G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91对于顶点着色问题，2-着色问题在多项式时间内是可解的。在多项式时间内解决了一些图类似地，对于某些类型的图，例如：区间图，弦图和可比图，确定χ（G）的问题也得到了有效的解决[18]。在所有这些情况下，特殊的结构（模式）已被发现，以表征类的图是着色的多项式时间复杂度。图的顶点着色是一个非常活跃的研究领域，有许多有趣的子问题.图着色问题在诸如调度问题、频率分配、规划等领域有许多应用[3，6，13]。在平面图的集合中，多边形链图一直是数学化学研究的一个相关问题，也许是因为它们表示用于表示化合物结构式的分子图[5，17，19]。同时，平面图在图论和绘图领域都占有重要的地位。事实上，平面图有几个有趣的性质：它们是稀疏的，四色的，它们的内部结构被简洁优雅地描述[4]。着色平面图是图和复杂性理论中的一个相关领域，因为它涉及到有效计算过程和复杂计算过程之间的边界。 例如，要确定平面图是否是3-可着色的，NP完全问题[9]。然而，著名的四色定理（4CT）[1，2]说，每个平面图是顶点4-可着色的。此外，4CT提供了一个多项式时间算法的顺序为O（n2）的4色任何平面图的n个顶点[2，16]。提出了一种新的平面图着色的贪婪算法。我们的建议是基于一个多边形数组的3-着色作为平面图上的着色的核心给出的约束的逻辑规范此外，在输入平面图G的内面图Gf上的预序遍历为我们构造图的内面的临界区域的部分极大独立集的集合提供了一种策略这些部分极大独立集的并集形成一个极大独立集S，它将（G-S）约简为一个3-可着色的多边形树。2预赛设G=（V，E）是一个无向简单图（即有限无环无重边图），其顶点集为V（或V（G）），边集为E（或E（G））.两个顶点v和w称为相邻的，如果有一条边v，w∈E，连接它们。x∈V的邻域为N（x）={y∈V：{x，y}∈E}，其闭邻域为N（x）<${x}，记为N[x]。注意v不在N（v）中，但在N[v]中。我们将集合A的基数表示为：|一|. 顶点x∈V的度，记为δ（x），|N（x）|. G的最大度，或者仅仅是G的度，是Δ（G）=max{δ（x）：x∈V}。从顶点v到w的路径是一系列边：v0v1，v1v2，. vn−1v n使得v = v0，v n=w，v k与v k+1相 邻 ，路径的长度为n。一G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9193简单路径是使得v0，v1，.，vn-1，v n都是不同的。一个循环只是一个非空的路径，其中第一个和最后一个顶点是相同的;一个简单的循环是一个循环，其中没有顶点是重复的，除了第一个和最后一个顶点。一个k-圈是长度为k的圈（它有k条边）。奇数长度的周期称为奇数周期，而偶数长度的周期称为偶数周期。没有圈的图称为无圈图。给定一个顶点子集S<$V，G的子图称为G的子图，其中S是顶点集，边集是{{u，v} ∈E：u，v∈S}，G由S诱导，记为G|S. G-S表示图G|（V−S）。 N（v）诱导的子图记为H（v）= G|N（v），它包含N（v）的所有节点和连接它们的所有边。一个独立的或稳定的集合是一个图中的顶点的集合，其中没有一个顶点与任何其他顶点相邻。也就是说，它是一个顶点集SV（G），使得对于任何一对顶点，都没有边连接它们。 的大小独立集是它所包含的顶点的数目。一个独立集是极大的，如果它不是另一个独立集的真子集，并且它是G中的最大的，如果在G中没有另一个独立集的基数大于|S|.一个图G=（V，E）的着色是给它的顶点分配颜色。一个着色是正常的，如果相邻的顶点总是有不同的颜色。G的k-染色是从V到集合{1，2，.，k}个k-可染性问题是指判定一个输入图是否是k-可染的.用χ（G）表示G的色数是使G有一个真色数的最小值kk-着色若χ（G）=k，则称G是k-色的或k-可染的.设G=（V，E）是一个图. G是一个二部图，如果V可以被划分为两个子集U1和U2，称为部集，使得G的每条边将U1的一个顶点连接到U2的一个顶点。若G =（V，E）是k-色图，则有可能将V划分为k个独立集V1，V2，…，V k称为颜色类，但不可能将V划分为k− 1个独立的集合。2.1平面图图G的一个绘图Γ将每个顶点v映射到平面的一个不同点Γ（v），将每个边（u，v）映射到一条简单的开Jordan曲线Γ（u，v），该曲线的端点为Γ（u）和Γ（v）。如果两条不同的边不相交（可能在公共端点处除外），则图形是平面的。一个图是平面的，如果它允许一个平面图。平面图形将平面划分为称为面的连接区域。无边界面通常称为外部面或外表面。如果所有的顶点都与外表面相关联，则平面图称为外平面图，并且允许它的图是外平面图。给定一个平面图，与每个顶点相关的边的（顺时针）圆形顺序是固定的。如果两个平面图形确定了与每个顶点相关的边的相同圆形顺序（有时称为旋转方案），则它们是等效的 （平面）嵌入是平面图的等价类，它由入射到每个顶点的边的顺时针圆形顺序描述。 一个图与它的一个平面嵌入放在一起有时被称为94G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91平面图一个非连通图是平面图当且仅当它的所有连通分支都是平面图。也许最著名的性质是欧拉定理所陈述的，它表明平面图是稀疏的。也就是说，给定一个有n个顶点，m条边和f个面的平面图，我们有n-m+f=2。一个简单的推论，可以从欧拉法则推导出的因为m=3n− 6，所以对于任何平面图，我们有m≤3n− 6。对于至少有三个顶点的极大外平面图，这个数减少到m=2n-m≤2n− 3（对于一般的外平面图）。此外，如果n≥3且图没有长度为3的圈，则m≤2n− 4。最后，如果图是树，则m=n−1。这些考虑允许我们在涉及平面图的任何渐近计算中用n代替m，而对于一般图，只能假设m∈O（n2）从更实际的角度来看，它们允许我们在不读取所有边的情况下确定密集图的非平面性。平面图的第一个完全特征是由Kuratowsky [11]提出的，并指出一个图是平面的当且仅当它不包含是K5或K3，3的细分的子图，其中K5是5阶完全图，K3，3是在划分的每个集合中具有3个顶点的完全二部图。一个类似的结果是瓦格纳观察到这两个特征是不同的，因为一个图可以允许K5作为子图，而不需要一个子图是K5的一个细分。3平面图的从现在开始，我们只考虑平面图作为工作图。著名的四色定理[1，2，16]保证了所有平面图都是4-可染的。然而，目前已知的4CT的证明是计算机辅助的。此外，证明的正确性仍然是冗长和复杂的[10]。另一方面，根据Grüotzs-ch定理[ 7 ]，任何无三角形的平面图都是3-可着色的。类似地，很容易（在图的大小的线性时间内）识别输入图是否是2-可着色的，因为它涉及识别图中循环的奇偶性，例如，如果它有偶数循环。在同样的意义上，所有的无环外平面图都可以只用三种颜色着色[15]。因此，识别3-可着色或4-可着色平面图的困难部分是当它们包含三角形时，因为这两种情况下都存在平面图例如，任何包含K4或奇数轮的平面图将请求四种颜色来正确地为这些图着色。然而，这些模式并不是唯一的4-着色情况。如果我们组成两个（或更多）轮共享一个三角形，并添加一条边连接每个轮的最后一个三角形的顶点，我们可以形成3或4-着色平面图。在本节的剩余部分，我们将介绍G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9195这些概念是我们在算法提案中开发出来的。我们考虑作为输入的平面图G=（V，E）的绘制已经嵌入在平面中。令Tres={ 1， 2， 3}是要使用的三种可能颜色的集合。对于每个顶点x∈V（G），一组禁止的颜色与它相关联，用Tabu（x）表示。下面的引理提出了一种非循环分支的3-着色方法，其顶点最多有一个禁止的颜色。引理3.1一个顶点最多有一种颜色的非循环分支是3-可着色的。证据非循环分量被认为是一棵以v r为根的树。一个前序着色由vr构成，其中Color（vr）=MIN{Tres−T abu（vr）}。当在每个要着色的新层中按前序前进时，新层中的所有顶点y将从其父节点最多具有两种受限颜色，并且颜色可以存在于Tabu（y）中。因此，它一直是可用的三种颜色的可能在三。当树的所有节点都已经按预定顺序被访问Q我们把上述无圈图的着色过程称为ISAT（G）过程.平面图G具有一组闭非连通区域R={r1，.，rk}称为面孔。每个面ri由界定其内部区域的边的集合表示。图G中的所有边{u，v}如果不是图G中某个面的边界，则用它的顶点uv表示，它们称为非循环边。如果两个面ri，rj∈R有公共边，则它们相邻，即E（ri）∈ RE（rj）否则，它们是独立的面。两条循环边相邻如果它们共享一个共同的端点。 一条非循环边与一个区域ri相邻，如果只有一个公共顶点一组面是独立的，如果每一对面都是独立的。引理3.2设A ={f1，f2，...，f n}是n个面的集合，其中每个面具有不限制颜色3的至少一个顶点。如果一组面是独立的或者它们都有一个公共顶点，那么A是3-可着色的证据这个引理是通过对集合中的面的数目的归纳来显示的。(i) 一个单一的面是3-可着色的，因为每个至少有一个不受限制的顶点的圈都是3-可着色的。(ii) 假设对n-1张面孔的假设成立。(iii) 设A是n个面的集合，其中每个面至少有一个顶点不限制颜色3。如果有一个面fa∈A与A中的所有其他区域无关，由于fa是3-可着色的（如情况1），fa可以从A. A中剩下的集合有n-1个面，归纳假设成立。否则，A中的n个 面共享公共顶点。 设x∈fi：∈fi∈A为公共顶点. 如果3∈/T abu（x），则通过将颜色3赋给x并将其从图中移除，A中的所有面变为开放的并形成非循环图，根据引理3.1，该图是3-可着色的。96G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91设T abu（x）={3}，但如果 i∈A，则 yi∈V（ fi ），则T abu（ yi ）={3}，通过定理证明.通过将颜色3分配给这些yij中的每一个，并从每个V（f i）中消除它们，形成非循环分量。这个分支可以通过引理3.1 3-着色。Q引理3.3对任意顶点v ∈ V（G），N [v]是δ（v）+1-可着色的.证据假设所有的y∈N（v）都有彼此不同的颜色。然后，v有δ（v）个邻域颜色，它只能从它的邻域中取一个不同的颜色，所以N[v]取δ（v）+1个颜色。如果在v的邻域中有重复的颜色，则最多需要使用δ（v）种颜色;因此，N[v]是δ（v）+1-可着色的。Q前面的引理适用于任何最小度的顶点（例如小于3），3种颜色足以被着色。之后，它可以在任何4-着色算法的开始被删除这个引理允许我们只考虑相邻面之间的一条边，因为相邻面之间的两条以上的边意味着2次顶点可以收缩到两个面之间公共边界的任何极值点。我们从G建立一个内面图Gf=（X，E（Gf）），如下所示：(i) 每个面ri∈R都有一个节点x∈V（Gf），由它的组成边来标记。(ii) G的每条非循环边都连接Gf的一个节点，该节点用其顶点的标号来标记.(iii) 存在连接Gf的两个相邻结点的边{u，v} ∈E（Gf），当它对应的面（或非循环边）在G中相邻时.(iv) Gf中的每条边由两个相邻节点之间的公共元素（顶点或边）标记Gf称为G的内面图。注意Gf不是G的对偶图，因为在Gf的构造中不考虑外部面。还请注意，Gf是一个平面图，其节点表示G的面，但它不一定是树图。然而，如果Gf具有树拓扑，则我们得到了G的着色的一个相关性质。当Gf是一棵树时，我们说G（它的对应平面图）是一棵多边形树。这意味着，虽然G有圈，但所有这些圈都可以排列成一棵树，其节点是多边形而不是G的单个顶点。在这种情况下，平面图的面的访问顺序为G的3-着色提供了有效的方法。文[12]证明了多边形树是3-可着色图。4平面图在这一节中，我们提出了一个多项式时间启发式染色的平面图G的基础上的建设的一个最大独立集的当前子，G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9197图G。我们假设输入图G是平面的，并且已经提供了G使得δ（v）3，v从G中移除，因为这些顶点是3-可着色的（基于引理3.3）。<这意味着面之间的两条以上的边被减少为一条，因为中间顶点的度为2。因此，一个新的平面图G是由其余的顶点和边形成的。然后从G构造内面图Gf在对顶点着色之后，检查算法的停止条件。此类停止条件为：i) 如果得到的图是非循环的，则应用ISAT过程来执行2-着色。ii) 如果生成的图是多边形树，则它是3-可着色的[12]。iii) 如果生成的图不包含三角形面，则根据Grüotzs c h定理，它是3-可着色的。我们的算法的目标是选择一个初始区域G开始着色顶点的过程为此，我们在面图中寻找具有最大度的区域（面）fr当这样的区域被识别时，我们搜索最大度的顶点xa∈V（fr），使得它可以首先被着色，即：f（xa）=color（xa）;y∈N（xa）：Tabu（y）=Tabu（y）<${f（xa）}。一旦选择了第一个顶点xa和颜色c，S=S{xa};Ga=G−{xa}。一个迭代过程的目的是建立一个最大的独立集S从Ga开始从fr。fr现在是遍历G f的根节点，其中该遍历的顺序是访问相邻面之间的公共边。我们在Gf的遍历过程中访问相邻的面，以建立由相邻面之间的公共顶点形成的最大路径。在我们的建议中的主要策略包括在建立一个最大的独立集S的G，以形成一个颜色类。然后，我们检查（G-S）是否是一个最多可以用3种颜色着色的非循环或多边形树图。在S的构造结束时，检查剩余的图（G-S）。如果Gf中没有圈，则G−S是3-可着色的。否则，如果过程返回一个新的图（G-S），其中有一个奇数长度的面，并且它们的所有关联顶点都被限制为颜色1，则输入图G是4-可着色的。我们的建议可以用下面的伪代码来描述98G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91−算法13-着色要求：一个平面图G。确保：图G具有有效着色。一曰： 标记图G第二章： 图Gf（G的内面图）3：S= Max Ind Set（G）; G中颜色为1的顶点的最大独立集。四： GJ=G S5：如果GJ是一个基本情况（非循环图或多边形树），则6：继续。7：其他8：S =最大Ind设置（GJ）; GJ= GJ− S。9：如果结束10：如果GJ包含一个奇数圈，其顶点被颜色1限制，则11：X（GJ）= 4;退出12：其他13：应用ISAT过程以将有效着色分配给GJ十四： end if15：将集合SJs与GJ连接起来，保持它们相应的颜色。算法2极大独立集（G）：构造G的极大独立集要求：一个平面图G和它对应的内面图Gf确保：S-G一曰： 当至少有一个顶点没有颜色和没有禁忌标记时，2：选择属于G中无颜色且无Tabu标记的奇数面的最大数目的x∈V（G3：选择y∈V（Gf）为Gf中的高次顶点，其中x属于它的关联顶点。4：基于x并通过面y的边遍历来构建V（G）的最大独立集。5：对于 每个u∈Sj，在最后一步中形成的集合做6：用颜色1标记u7：对于 每个u顶点都着色，8：用禁忌1标记N（u9：结束10：结束11：如果G是一个基本情况（非循环图或多边形树），则12：返回S，S是已经计算的部分最大独立集之间的合取。13：如果结束14：结束时15：返回S，S是已经计算的部分最大独立集之间的合取。G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9199101213762985461011115312 1512413149161778123456789 10 111512 13 1416 1717 85 610 11362912411 12 151314169 17876 789 10 111512 13 1416 17让我们在下面的平面图G上说明我们的建议（图1）第一步是标记输入图G的面。然后，利用图G的内面标号，构造图G的内面图GfFig. 1. 具有可识别面的图G图二. G的内面图Gf在迭代过程中，选择属于G中奇数面数量最多的顶点x∈V（G）在我们的例子中，顶点10∈V（G）被选择。同时，选取Gf中度较高且包含所选顶点x的顶点y∈V（Gf）在我们的例子中，选择面2∈V（Gf）。然后，考虑10∈V（G）作为第一个顶点，将形成一个极大独立集因此，从V（G）中移除顶点10。由于结果图不是基本情况（非循环或多边形树），因此重复迭代步骤。图三. 无顶点10的图G图 4.图3中的图的内面图Gf同样，属于最大奇数面数的顶点x∈V（G）在G中，选择Tabu（x）=0。在这种情况下，选择顶点12∈V（G）和与x关联的较高次顶点y∈V（Gf）。这选择顶点10∈V（Gf）。在下一步中，我们考虑形成面10的顶点来扩展部分最大独立集。在这种情况下，顶点12∈V（G）。因此，用顶点10和12形成部分最大独立集。这些顶点从G中移除，如图5所示100G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9116297 8563 1112X4169 17876789X12 1617图五. 无顶点图G{10， 12}图 6.图5中的图的内面图Gf我们检查结果图是否是一个基本情况（非循环或多边形树）。由于没有获得基本情况，我们的过程执行另一次迭代。在这种情况下，必须形成一个新的独立集，因为G中所有剩余的顶点xh av e T abu（x）.我们寻找G中奇数面数最多的顶点x。顶点2∈V（G）满足上述条件。我们从图中删除这些顶点，如图7所示在这种情况下，生成的图形标记了所有G中的剩余顶点v。然后我们考虑建立另一个颜色类。为此，我们从所得图G中选择面Y∈Gf，因为它是Gf中的高次顶点。在下一步中，我们在符合面Y的顶点之间建立部分极大独立集。在此迭代期间形成的部分最大独立集是{4，1， 7}。我们从图中删除这些顶点，如图8所示在这种情况下，结果图是基本情况。由于它是非循环的，我们的过程停止并返回由 S1={ 10， 12， 2}和S2={ 4， 1， 7}形成的两个最大独立集。见图7。 无顶点图G{10，12，2}图八、图G无顶点{10， 12， 2， 4， 1， 7}最后，应用ISAT过程对无圈图进行着色。其结果是，我们得到了一个4-着色的输入图。185631112Y491617786531198G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91101987654321101213762854691011531112 151213 1449716 178图第九章G的最终染色我们的建议的主要贡献，这是不同的其他建议在艺术状态，是：a) 的内部图形的面Gf被用来作为一个监控系统，在选择最好的顶点着色，以及检查算法的停止条件。b) 我们的建议是基于识别出现在奇数个三角形面中的顶点作为第一个着色的关键元素c) 我们应用禁忌搜索，以限制顶点的着色选项d) 我们利用的事实是，每个颜色类是一个独立的输入图集因此，部分极大独立集是形成颜色类的基础。我们考虑另一个例子来说明我们的建议。见图11。 G的内面图Gf见图10。 具有可识别面的图G在我们的算法中的一个相关的策略是考虑顶点出现在最大数量的奇面G的最大独立S的一部分，以建立。例如，根据图10和图11中的图，两个最大独立集是：S1={ 2， 4， 6， 8}和S2={ 1， 4， 7， 11}。然而，S2包含196 5510 472311182698743102G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91顶点11，它出现在G的奇数面的最大数目中。 因此，S2是比S1更好的选择。在移除已经着色的顶点之后，获得基本着色情况图（应用ISAT），这使得它成为3-可着色实例。-3图12个。将颜色1添加到S的顶点图十三. （G-S）的2-着色及其ISAT方法值得注意的是，最大独立集必须符合前面描述的特征。如果不这样做，那么使用的颜色数量可能高于所需的数量。为了证明这一点，考虑集合S={ 2， 4， 6， 8}开始图的着色，如图14所示。然而，得到的子图（G-S）是一个3-可着色的实例，如图15所示图14个。 将颜色1添 加 到S 的顶点图15. （G-S）的3-着色图15中的图表明（G-S）是一个3-可着色图;因此，使用4种颜色来着色G。 请注意，集合S的任意构造可能会导致冲突，因为它可能会留下一个奇数循环，其所有顶点都具有相同的颜色限制。这产生了在图G的着色中使用的颜色的数量的增加。我们将我们的建议与Nishizeki等人的着名算法进行比较。[14]，该算法保证最多用五种颜色对平面图进行西关1651072119843-3-365102-3-398-33-31510119165107211984373G. De Ita Luna等人/理论计算机科学电子笔记354（2020）9110316510721198431651072119843提出了一种基于五度顶点识别的算法。如果找不到这些顶点，则从较高度数的顶点递归着色。着色的顶点将从图形中移除。重复该过程，直到图只有5个顶点，以便授予任意着色。该算法的执行如下图17所示。可以看出，Nishizeki的算法在不必要时执行4着色。与此同时，我们的建议授予三个着色。图十六岁用我们的算法实现G的最终染色图17. 基于Nishizeki算法的G4.1时间复杂度分析让我们考虑一个输入图G=（V，E），其中n=|V|和m=|E|.我们分析了算法2（最大独立集过程）的时间复杂度。 基于对G的深度优先搜索，可以在O（m+n）阶的时间内识别G中的圈的奇偶性。为了选择由x形成的面（步骤3），需要O（f）阶的时间。 在最坏的情况下，它的顺序是O（m），当一个面G的最大长度。算法2中的两个为了识别图G是否具有奇数圈或者它是否代表我们建议的基本情况，它可以在线性时间内对104G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91因为它基于对图G的深度优先搜索的应用和G中基本圈的识别。 这个过程中最昂贵的一步是检查部分极大独立集的所有顶点上的独立性的约束。在最坏的情况下，它需要O（n2）的时间。 算法2的时间复杂度为O（n2）.算法1涉及G的内面的构造，已知其需要O（m+n）的时间。为了检查奇数圈的所有顶点上的限制，它可以在时间O（n）内完成，基于禁忌集。在我们的建议中，最昂贵的时间过程是最大的Ind集，其时间复杂度为O（n2）阶的过程。我们的建议最多执行两次对Max Ind Set的调用。因此，我们的建议有一个时间复杂度为O（n2）的输入图G的大小。我们的建议，以及Nishizeki然而，Nishizeki5结论给出了一个时间复杂度为O（n2）（n我们的建议是基于关于从输入图G计算极大独立集S。极大独立集S具有一些特征。其中之一是S包含出现在G的最大奇数面数中的顶点。此外，S的构造考虑了输入图G的内面图，以便选择属于G的最大数量的奇面的每个顶点。计算图的内面上的部分极大独立集的集合。这些部分极大独立集的并集构成G的极大独立集S。它允许我们首先对图GJ中对分解输入平面图至关重要的顶点进行着色，其中两种颜色足以对GJ进行着色。即（G-S）是2-可着色的，或者在其他情况下，我们的程序识别出G是4-可着色的。引用[1] K. Appel和W.哈肯每幅平面图为四列，第一部分：放电。伊利诺伊数学杂志，第21卷，第429 -490页，1977年。[2] K. Appel，W.哈肯和J.科赫。每一个平面地图是四列，第二部分：归约。伊利诺伊数学杂志，第21卷，第491 -567页，1977年。[3] J.M.拜斯科夫图着色和精确满足性的精确算法。博士论文，阿布斯大学，丹麦，2005年。[4] P. Cortese和M.帕特里尼亚尼平面性测试和嵌入，Press LLC，2004年。[5] T. Dosl i'c和F. 我来了。 链状六角仙人掌：镶嵌环和指数集。数学，卷310，页。1676-G. De Ita Luna等人/理论计算机科学电子笔记354（2020）91105[6] Z. D vora'k，D. Kr'al和R. 托马斯曲 面 上的三色无三角形 图。在 ：第20届ACM-SIAM离散算法研讨会上，pp。120-129，2009年。[7] H. Gr？otz c h. EinDreifar benforcefurdreikreisfreieNetzeaufderKugel. 聪明Z. 马丁-路德-哈雷-维滕贝格数学大学自然。Reihe 8，pp. 109-120，1959年。[8] F. Haray和W. T.图特Kuratowski定理的对偶形式。加拿大数学通报，第8卷，第17 -20页，1965年。[9] D.约翰逊NP完全性专栏：持续指南。Jour. Of Algorithms 6，pp.434-451，1985.[10] K. Kawarabayashi和K.关4-着色3-可着色平面图的一个简单算法计算机科学，第411卷，pp。2619[11] K.库拉托斯基关于拓扑学中的断层问题。基金数学第15卷，271 -283页，1930年。[12] C. Lopez，G.De Ita和A.奈里通过增量可满足性建模多边形树的3-着色LNCS 10880的模式识别，Springer Verlag，93-104，2018。[13] G.B. Mertzios 和 P.G. 小 直 径 图 3- 可 染 性 的 算 法 和 几 乎 紧 结 果 。 技 术 报 告 。 2012 ，arxiv.org/pdf/1202.4665v2.pdf。[14] T. Nishizeki和N.千叶《平面图：理论与算法》，Elsevier，第32卷，pp.83-87，1988年。[15] A. Proskurowski和M. Sylvia。外平面图的有效点染色和边染色，Siam J. Alg. Disc. 方法论，第7卷，第1卷，第131 -136页[16] N.罗伯逊，D.P.桑德斯，P.D. Seymour和R.托马斯。四色定理。Journal Combinatorial Theory Ser. B，volume 70，pp.2-44，1997.[17] W.C.阿秀六角蜘蛛的极值Hosoya指数和Merrifield-Simmons指数离散应用数学，第156卷，2978-2985，2008年。[18] J·斯塔乔3-在多项式时间内对无AT图着色。 In：Cheong，O.， Chwa，K.-是的， 帕克，K.（编辑）算法和计算，ISAAC-LNCS 6507，pp。144-155，2010，URL：https://doi.org/10.1007/978-3-642-17514-5。[19] S. 瓦格纳和我古特曼Hosoya指数和Merri field-Simmons指数的最大值和最小值应用数学学报，第112卷，323-346，2010年。