| 关于平面图的3-选色 |
| |
| 引用本文： | 吴桂月,王雪梅.关于平面图的3-选色[J].淮阴工学院学报,2007,16(5):22-25. |
| |
| 作者姓名： | 吴桂月 王雪梅 |
| |
| 作者单位： | 中国矿业大学,理学院,江苏,徐州,221008 |
| |
| 摘 要： | 图G的选色数记为ch(G),定义为最小的自然数K,使得满足:对于任意顶点给定的K种颜色列表,染色时每个顶点的颜色只能从自身的颜色列表中选择时,图G的顶点总存在一个正常着色。我们证明了每个围长至少为4且不含5-,8-和11-圈的平面图是3-可选色的,以及每个围长至少为4且不含6-,9-和10-圈的平面图是3-可选色的。
|
| 关 键 词： | 平面图 3-选色 围长 |
| 文章编号： | 1009-7961(2007)05-0022-04 |
| 修稿时间： | 2007年8月30日 |
On 3-Choosability of Plane Graphs |
| |
| WU Gui-yue,WANG Xue-mei.On 3-Choosability of Plane Graphs[J].Journal of Huaiyin Institute of Technology,2007,16(5):22-25. |
| |
| Authors: | WU Gui-yue WANG Xue-mei |
| |
| Abstract: | The choice number of a graph G,denoted by ch(G),is the minimum number of ksuch that if we give lists ofk colors to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are.In this paper,we show that ch(G)=3 for each plane graph of girth no less than 4 which contains no 5-,8-and 11-cycles and =3 for each plane graph of girth no less than 4 which contains no 6-,9-and 10-cycles. |
| |
| Keywords: | plane graph 3-choosability girth |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
