论文总字数：15160字

摘 要

图染色问题是图论的中心话题。随着四色猜想的提出，图论的研究越来越深入，图论的相关概念也越来越多。

二十世纪七十年代，列表染色的概念的被提出。这使得点染色得到了推广。

尽管如此，但是列表染色却有着无法使用一些非常重要的技术的缺陷（例如，顶点粘合），使得一些猜想的解决被加以限制。为此，DP-染色的概念被提出，解决了这一窘境，使得图的染色更丰富，并且推动了图染色的发展。

在第一部分，会介绍点染色和列表染色的相关概念以及研究成果，并说明列表染色是点染色的推广。第一部分的末尾介绍图论的相关概念。到第二部分，本论文会对对应染色的定义进行介绍以及说明对应染色推广了点染色，并在最后介绍一些对应染色的研究成果。第三部分将会对可约结构和权转移法进行介绍。

在第四部分，我们将用权转移的方法证明不含{3,4,5,7}-圈的平面是3-对应可染的。从而在第五部分进一步探讨不含{3,4,7}-圈的平面图相关的的平面图的3-对应染色的情况。

关键词：对应染色，平面图，圈，权转移

Abstract

Graph coloring is a central topic in graph theory. With the proposal of the four-color conjecture, the research of the graph theory is more and more in-depth, and the related concepts of graph theory are also more and more. Therefore, the concept of DP-coloring is proposed, which solves this dilemma ,enriches the graph coloring,and promotes the development of graph coloring.

In the 1970s, the concept of list coloring was proposed. This is generalization of vertex coloring. However, list coloring has the disadvantage of not being able to use some very important techniques, which limits the solution of some conjectures.

In the first section, the concepts and research results of vertex coloring and list coloring will be introduced, and explains the list coloring is the extension of the vertex coloring. The related of graph theory are introduced at the end of the first section. In the second section, this paper will introduce the definition of dp-coloring and explains the dp-coloring is the extension of the list coloring. Some research of dp-coloring are introduced at the end of the second section. The third section will introduced reducible configurations and the discharging.

In the fourth section, we prove that the planar graphs without {3,4,5,7}-cycles is dp-3-cloroable. In the fifth section, the dp-coloring of planar graphs without {3,4,7}-cycles is further discussed.

KEY WORDS:DP-3-coloring,planar graph,cycle,discharging

目录

摘 要.........................................................................................................1

ABSTRACT.............................................................................................2

第一章 导言......................................................................................4

1.1正常点染色及其研究情况………………………………………………................4

1.2列表染色及其研究现状…………………………………………………................4

1.3图的基本定义和符号的表示……………………………………............................5

1. DP-染色的定义及现状........................................................7

2.1 DP-染色的两种定义…………………………………………………….................7

2.2 DP-染色的研究现状…………………………………………………................….8

第三章 可约结构和权转移法的简要介绍......................................9

3.1主要引理及可约结构………………………………………………................……9

3.2权转移法………………………………………………………………..................10

第四章 不含{3,4,5,7}-圈的平面图............................................10

第五章 不含{3,4,7}-圈的平面图....................................................11

5.1不含{3,4,7}-圈的平面图的结构讨论……………………………………..............11

5.2平面图只有3-顶点的情况讨论……………………………………….................12

5.3限制后的不含{3,4,7}-圈的平面图的DP-3染色………………………................14

参考文献..........................................................................................17

致 谢................................................................................................19

导言

图染色问题是图论的中心问题。图的染色分为点染色和边染色，图有有向图和无向图之分。本文研究的是无向平面图的点染色问题。图论（Graph Theory）是数学的一个分支，也是一门新兴学科，发展迅速而又应用广泛。它已广泛应用于物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络管理、社会科学等几乎所有的科学领域，另一方面，随着这些学科的发展，特别是计算机科学的快速发展，又大大的促进了图论的发展。图论中的染色问题十分经典，它最初源于人们对“四色猜想”的证明的尝试。此后关于图的染色问题的研究十分火热。点染色在实际生活中有着广泛的应用，例如计算器编译一个程序分配寄存器、无线交换设备的波长分配、信号分配等。因此对点染色问题的讨论不光具有重要的理论意义，而且还有十分重要的实际意义。本文主要探究平面图的点染色问题，讨论没有{3、4、5、7}-圈的平面图是否可以DP-3染色，以及不含{3、4、7}-圈的平面图的情况。

1.1正常点染色及其研究情况

图的点染色，就是使得一个图相邻两个顶点具有不同的颜色。我们用不同的符号来表示不同的颜色，若一个图染色用了种符号，则它存在一个正常—染色，即说明它是—可染的。关于点染色最经典的问题就是四色猜想，它指出每一个平面图都是4—可染色的。在1976年，在美国伊利诺斯大学的两台不同计算机上，用了1200个小时，作了100亿个判断，结果没有一张地图是需要五色的，最终证明了四色定理。我们让不同的数字表示不同的颜色，令函数。如果一个图存在一个正常—染色，但不存在一个正常—染色。我们把这个记为。

1.2列表染色及其研究现状

一个平面图是不是3—可染的，这是一个NP完全问题。为此，Grötzsch[6]证明了没有3-圈的平面图是3-可染色的。随着人们不断深入地研究。正常的点染色已经不能满足人们日益增长的研究需求，染色的定义和种类越来越丰富。到了二十世纪七十年代，Vizing[13]和Erdös，Rubin和Taylor[5]独立地引入了列表染色。这使得点染色得到了推广。令表示一个列表赋值，使得顶点可以在集合中选择自己的颜色。如果平面图存在一个正常—染色，对于染色函数有∈，则我们称该平面图是-可染色的。如果对任意的，，则我们说这个图是-可选的。如果一个图是-可选的，但不是—可选的，我们把这个用符号来表示。

请支付后下载全文，论文总字数：15160字