| 围长为4的平面图不总是3－可选色 |
| |
| 引用本文： | 沈明刚,朱忠华.围长为4的平面图不总是3－可选色[J].上海师范大学学报(自然科学版),1996(2). |
| |
| 作者姓名： | 沈明刚 朱忠华 |
| |
| 作者单位： | 上海师范大学数学系 |
| |
| 摘 要： | 针对ＫｒａｔｏｃｈｖｉｌＪ和ＴｕｚａＺ（１９９４）提出的问题：是否每一个国长为４的平面图总可以３－可选色（３－ｃｈｏｏｓａｂｌｅ）？用组合技巧构造了一个反例，从而证明了围长为４的平面图并不一定是３－可选色的，否定了每一个３－可着色的图一定是３－可选色的这个论断．
|
| 关 键 词： | 平面图 list着色 L－可选色（L－choosable） 3－可选色 k－可着色 围长 |
Not All Planar Graphs Are 3-Choosable |
| |
| Shen minggang, Zhu Zhonghua.Not All Planar Graphs Are 3-Choosable[J].Journal of Shanghai Normal University(Natural Sciences),1996(2). |
| |
| Authors: | Shen minggang Zhu Zhonghua |
| |
| Institution: | Department of Mathematics |
| |
| Abstract: | In 1994, Kratochvil J and Tuza Z raised the question of whether any planar graph of girth 4 is 3-choosable. We prove, by virtue of a counterexample, that not all planar graphs of girth 4 are 3-choosable. Thus 9 the assertion that any 3-colorable planar graph is 3-choosable is negated. |
| |
| Keywords: | planar graph list-coloring L-choosable 3-choosable k-color girth |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《上海师范大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《上海师范大学学报(自然科学版)》下载免费的PDF全文 |
