【作者】 江燕；

【导师】 李相文；

【作者基本信息】 华中师范大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 文章主要有两部分内容,一部分介绍选择着色,另一部分介绍对策着色。如果对于给定的一个序列分配L={L(v):v∈V(G)}图G存在一个正常着色φ,使得对每一点v∈V(G)都有φ(v)∈L(v),则称图G是序列L-可着色的,如果图G的每个点v∈V(G),对每一个序列分配|L(v)|≥k都是序列L-可着色的,则称图G是k-可选择着色的,我们在这篇文章中证明没有{4,6,7,8,9}圈的平面图是3-可选择着色的,另一部分介绍了一种新的对策着色和对策色数,比较了两种色对策的差异,对几种特殊图形的色对策进行了讨论,运用顶点标号法,给出了获胜策略。更多还原

【Abstract】 The article has tow main parts.PartⅠintroduces the choosability,another part introduces the game coloring chromatic number.A graph G is list L-colorable if for a given list assignment L={L(v):v∈V(G)},there exists a proper coloringφof G such thatφ(v)∈L(v)for each v∈V(G).If G is list L-colorable for every list assignment with |L(v)|≥k for all v∈V(G),then G is said to be k-choosable.We show in this note that every planar graph without any cycle of length in {4,6,7,8,9} is 3-choosable.In another part of this article,it introduces a new game coloring chromatic number and compares the differences between the two kinds of chromatic numbers.By labeling the vertices of graph, this article determines the chromatic number of several graphs.更多还原