| 图与其Mycielski图关联色数的关系 |
| |
| 引用本文： | 张丽,陈东灵,陈学刚. 图与其Mycielski图关联色数的关系[J]. 数学进展, 2006, 35(2): 171-177 |
| |
| 作者姓名： | 张丽 陈东灵 陈学刚 |
| |
| 作者单位： | 山东科技大学信息科学与工程学院,青岛,山东,266510 |
| |
| 摘 要： | 本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G) 1,则M(G)的关联色数为△(M(G)) 1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．
|
| 关 键 词： | 关联着色 关联色数 Mycielski图 猜想 |
| 文章编号： | 1000-0917（2006）02-0171-07 |
| 收稿时间： | 2004-04-05 |
| 修稿时间： | 2004-08-20 |
The Relationship Between a Graph''''s Incidence Coloring Number and Its Mycielski Graph''''s Incidence Coloring Number |
| |
| ZHANG Li,CHEN Dong-ling,CHEN Xue-gang. The Relationship Between a Graph''''s Incidence Coloring Number and Its Mycielski Graph''''s Incidence Coloring Number[J]. Advances in Mathematics(China), 2006, 35(2): 171-177 |
| |
| Authors: | ZHANG Li CHEN Dong-ling CHEN Xue-gang |
| |
| Affiliation: | College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao,Shandong, 266510, P. R. China;College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao,Shandong, 266510, P. R. China;College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao,Shandong, 266510, P. R. China |
| |
| Abstract: | In this paper, we prove that for any graph G of order n, if the twice of its maximum degree 2△(G) doesn't equal n and it's incidence coloring number xi(G) equals △(G) + 1, then the incidence coloring number of its Mycielski graph xi(M(G)) equals △(M(G))+1. We also study the incidence coloring numbers of Mycielski graphs of trees and complete bipartite graphs. At the end of this paper we pose a conjecture of the incidence coloring number of M(G), where M(G) denotes the Mycielski graph of the graph G = (V, E). |
| |
| Keywords: | incidence coloring incidence coloring number Mycielski graphs conjecture |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
