英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料
一类平面图的3-对应染色
概要：在这篇论文中，我们用一种统一的方法去证明一些种类的平面图是3-对应可染的，这将延伸3-可选性的相应结果。
1.导言
图染色问题是图论中的中心话题。图的正常是一个函数，使得相邻两个顶点之间具有不同的颜色。我们说是，如果它存在一个正常。如果存在正常，但不存在一个正常，则这个最小的我们用符号表示。著名的四色定理指出每一个平面图都是可以4-可染色的。
然而，决定一个平面图是不是能够3-可染色的是NP完全的，这给寻找3-可染色平面图的充分条件提供了动力。例如，Grouml;tzsch[11]证明了没有3-圈的平面图是3-可染色的。
Vizing[21]和Erdouml;s，Rubin和Taylor[10]独立地引入了列表染色作为一个正常染色的推广。一个列表赋值给每一个顶点一个可选择的颜色列表。图是，如果有一个正常的的染色满足对每一个有。图是如果对任意，其中，都是，最小的记为。
由于-可选性的定义，要求对于特别的，我们有le;。Voigt[22]发现了一个非4-可选的平面图，表明了这个不等式或许是严格的。Thomassen[19]
证明了每个平面图都是5-可选的，这给了这个类的一个上界。
对于平面图的3-可选性，平面图是3-可选的充分条件已经被研究。然而，这个问题更困难，Voigt[23]给出了一个没有3-圈的平面图不是3-可选的。另一方面，Thomassen[20]证明了每一个平面图没有3-圈且没有4-圈是3-可选的。一些其他的条件被包含在定理1.2。
列表染色问题一个困难是，一些用在染色中的重要技术在列表染色中是不可行的（例如，顶点粘合）。为了克服这一困难，Dvoaacute;k和Postle[9]引入了对应染色（DP-染色），使其作为列表染色的推广。
定义1.1. 设是一个有个顶点的简单图，是一个的列表赋值。对中的每条边，设是集合和集合之间的一个匹配，令，称其为匹配赋值。设是满足下列条件的图
bull;每个对应于中的点集合
bull;对所有，集合组成一个完全图
bull;如果，则和之间的边是的那些边
bull;如果，则没有边在和之间
如果包含一个大小为的独立集，那么有一个-染色。图是-对应可染色的，如果对每一个，满足，对任何匹配赋值，它有一个-染色。使得是-对应可染色的这个最小的，称为的对应染色数，用符号表示。
作为列表染色，我们用的元素作为颜色，并在-染色的独立集中选择的元素称为的颜色。
即使对所有限制，DP-染色也推广了列表染色。要看到这一点，考虑一个列表赋值，对所有有。我们可以建立一个和之间的双射，让作为一个和之间的颜色匹配，和的颜色分别相关于和的元素。考虑到重新标记，这个-染色等价于一个-染色。因此，le;。然而DP-染色和列表染色是可以十分不同的。例如，Bernshteyn[2]表明平均度为的每个图的对应染色数是，而Alon[1]证明了并且界限是严格的。
Dvoaacute;k和Postle[9]使用这种标记法证明了任意一个没有从4到8圈的平面图是3-可选的（实际上通过对应染色可证得更强的结论），解决了Borodin[8]的一个由来已久的猜想。自此以后，越来越多的关注在这个新染色上，见例子[2,3,4,5,6,7,12,13,14,18]。
我们对平面图的对应染色很感兴趣。Dvoaacute;k和Postle[9]指出Thomassen对可选性的证明可以用来表明平面图的，且没有3圈和4圈的平面图的。在[12]，[13]，[18]给出了平面图是4-对应可染色的充分条件。
我们研究平面图是3-对应可染色的充分条件。对平面图3-可选许多这样的条件是已知的，其中一些条件在定理1.2被列出。
定理1.2. 一个平面图是3-可选的，如果他符合下列条件
bull;不含{3,6,7,8}-圈。（[17]，2009）
bull;不含{3,5,6,}-圈。（[15]，2005）
bull;不含{4,5,6,9}-圈。（[25]，2005）
bull;不含{4,5,7,9-圈。（[24]，2004）
bull;不含{5,6,7}-圈并且三角形的距离至少为2。（[16]，2016）
我们表明这些条件也是一个平面图是3-对应可染色的充分条件。
定理1.3. 在定理1.2所列出的任意平面图是3-对应可染色的。
结果的证明使用了权转移法，为此使用了强归纳法。如果一个结构不能出现在最小反例中则说它是可约的。很快能发现定理1.2的所有证明非常依赖下列的事实：顶点都是3度的偶数圈是可约的。换句话说，如果是顶点都是3度的偶数圈，则任何的染色可以推广到。这是因为偶数圈是2-可选的。然而这种结构对3-对应染色的结果来说是不可约的，因为偶数圈可能不是2-对应可染色的，如图1所示。
图1：一个4-圈不是2-对应可染色的：左图是4-圈，右图是图。
因此，我们需要新的想法来达到我们的目标。我们将通过权转移法表明，这些平面图包含一个“近--退化”子图，像引理2.2表述的那样的是可约的。引理2.2更一般地说是为了对-对应染色给出一个可约结构；这种结构的特殊形式（被命名为theta子图）是证明[12, 13, 18]中的基本组成部分。
本文结构如下。在第2部分，我们提供了基本的定义，并证明了所有证明中所需的基本可约结构。在下列的每一个部分，我们会给出定理1.3的部分证明。
可约结构和权转移法的简要介绍
在本文提及到的图都是简单图。-顶点（-顶点，-顶点）是度顶点（至少为度，至大为度）。一个面的长度是它的边界的顶点数，重复的按重数计算。我们会涉及到一个（）-面是一个路为的-面，满足。
2.1 可约结构
引理2.1. 设是最小的（与其顶点数相关）不是-对应可染色的图，则。
证明 设是一个的顶点。任何的-染色可以推广到，因为至多有个颜色被禁止，而。
设是的一个子图。对每个顶点，设是在中的顶点集，它们不是中的顶点的邻点。人们可以认为被染色后，是可用的颜色集合。
引理2.2. 设并且是的一个子图。如果的顶点可以被排序为，且满足下列三条
- 且，
- )且在中至少有一个邻点，
- 对任意,至多有个邻点在中，
那么的-对应染色可以被推广到的-对应染色。
证明 对所有，建立一个匹配赋值，，且建立一个的染色。因为条件（2），在有一个邻点，所以颜色被它在中的邻点禁止使用。现在根据（1）我们可以选择一个颜色，在中不匹配，或者不匹配中的任何颜色。然后我们可以给按顺序涂上颜色，因为根据（3），当我们操作时，至少有一种颜色可用。选择的保证了也至少有一个颜色可用。 □
在面上的一个-通路是沿的面的路的连续顶点集，。我们允许任何一个被和代替，以分别表示，。一个面可能包含一个割点，因此重复顶点在通路上是可能的。如果顶点不同，我们也称它为一个-路。当时，我们有时称它为一个-边。当，我们说边控制穿过与相邻的面。我们将此概括为-通路控制在上与相邻的面。在一个上的一个-顶点（），如果在上的的两条边都没有控制一个则它是富于，如果他们当中的一个控制一个则它半富于，如果他们控制两个则它穷于。
在我们的证明中，我们将经常考虑到每一个受控面是的()-通路。因为这个原因，如果每个它控制的面都有长度（或最大为或最小为），我们说一个()-通路是-控制。此外，我们说一个()-通路是极大的，如果它是-控制，但是的边在其前后直接地控制-面。
设是一个-面。我们使用表示不在的-控制路上的的顶点数，表示半富-顶点的个数加上被控制的-面（该面至少有两个-顶点）的个数和被控制的-面（至少有3个-顶点）的个数的数。我们也让作为具有个内部顶点的极大-控制通路的数目（当的每条边控制一个-面时，我们将路的内部顶点数目视为）。因此
- .
如果上下文清楚，我们通常写作分别表示,,。
对于我们主要的可约结构，我们关注的是()-路的特殊类型。
定义2.3. 一条,...,是特殊的，如果
bull;对每个，有一条路=，的内顶点都是3度点
bull;且。
图2：10-圈：含有一条3-控制特殊（3,4,3）-路，一条特殊（4,4,4,3）-路，和一条不特殊极大（3,4,3）-路（此路含一条特殊（4,3）-路，且此路有两个（3,4,3）-路的顶点）。
在我们的证明中，我们将通常考虑这种情况：的是沿着,...,被控制的面的边界组成的，但是这不是一般的情况。
通过应用引理2.2于一个子图，我们发现，含弦圈是可约的，如果这个圈的每个点的度均为3且至少有一个外部邻点。一个外部邻点的条件要求是引理2.2所必须的。这个条件也是普遍必要的，因为是有一个有2条弦的3-顶点的4-圈，且每个点的度为3度。然而，引理2.2也应用于一个巨大的圈族。在3-度点圈的弦被延伸为允许一个（3，4，...，4，3）-路，尽管我们要求这条特殊的路以特定的方式和一个外部点相邻。它也允许这个圈有半富4-顶点，只要这些4-顶点属于遵循圈定向的特殊。
引理2.4 假设不含相邻的-圈，且不是3-对应可染色的，而的每个真子图是3-对应可染色的。设是中的一个-面，且含一条特殊的（3，4，...，4，3）-路。如果每一个控制的-面，的每个不在上的顶点有一个邻点在和控制的-面组成的子图外，则下列其中一条成立：
（i）含一个-顶点或一个富4-顶点；
（ii），且当且仅当含一条有且仅有一（4,4）-边控制一个或一个（的（3，4，...，4，3）-路；
（iii）除此之外，如果除以外的所有极大路都是，那么含至少一个半富4-顶点，且如果只有一个，则它在一个至少有两的上。
证明 假设（i）,（ii）,（iii）都不成立，则不含-顶点或一个富4-顶点，或，，且每一个的（4,4）-边控制一个而没有其他，或除了所有的极大路是（3,3）-路，或除了所有的极大路是（3,3）-路和一特殊（3,4）-路。因此在上的-顶点是穷或半富4-顶点，且至多有一半富4-顶点。且如果与一个被一条（3,4）-边控制且有一-顶点不在上的相邻，则不含半富4-顶点，且被一条（3，4，...，4，3）-路控制。在后一种情况，我们将划分路为一个3-顶点和一条特殊（4,...,3）-路。所以我们可以假设由3-顶点和至多有一个半富4-顶点的路组成。
设。我们设定在上的顶点和被的边控制的一些面的顺序如下：
bull;初始列表是，是在特殊（3,...,3）-路上的一条。
bull;对每一，设=在被控制的-面上，然后将中除之外的所有点加入，除非在一个（3,3）-路上。
bull;设是在被控制的-面上从到的路。将中除之外的所有点加入。
bull;我们设特殊（4,...,3）-路的半富4-顶点是在列表中路的顶点之间的最低指数顶点。（请注意，这是有效的，因为可以在相反的顺序中选择。）
我们将最后的列表用表示。没有重复的顶点，在以外没有邻点，且最后的顶点有一个以外的邻点。通过这个结构，每个在中的顶点是3-顶点，每个在中的顶点至多有两个及这点之前的的邻点。因此通过引理2.2，的3-对应染色可以推广至，矛盾。 □
2.2.权转移法的简要讨论
在本文中，在下面的每一节中是一个最小反例。我们用表示中顶点或面的初始权，用表示权转移过程后的最终权。在我们所有的证明中，我们对每个顶点有函数，对每个面有函数。然后，通过欧拉公式
由引理2.1，为了3-对应染色，只有面开始于负权。我们让权在周围移动，认为每个顶点和面以非负权结束。由于权只是移动，这一矛盾证明了我们的结论。
由于只有有负的初始权，我们使用以下规则给它们足够的权。
每个从在其上的每个获得一个权，其剩余部分均匀从与之相邻的均匀获得。
请注意，可能与共用多个边，特别是当包含切割顶点时。在这种情况下，我们要求使其剩余部分均匀地通过与其相邻7-面的边缘。
现在上的和一些可能有多余的权，我们将让他们按照一些不同的规则、等从一个设置到另一个设置给，这将在随后的每一节中具体说明。尽管如此，一些特别的可能仍然有负权，我们创建一个储库向他们发送权，即、等。不过，并不是每个设置都需要使用储库。
不含{3、6、7、8}-圈的平面图
作为热身，我们证明定理3.1。尽管出现了更复杂的情况，在后面的部分中使用的转移规则在本质上与证明中使用的规则相似。
定理3.1. 没有{3、6、7、8}-圈的平面图是3-对应可染色的。
证明 我们首先观察到，如果两个是相邻的，那么它们必须是两个，共享一个公共边和一个，而一个不能与两个相邻。
注意，一个是邻接的，分别邻接2，3和个。通过，每个顶点都有非
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[246373]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
