摘要
本文证明了对n阶图G,若其最大度△(G)的2倍不等于n,且G的关联色数等于△(G)+1,则M(G)的关联色数为△(M(G))+1．同时还研究了树和完全二部图的Mycielski图的关联色数．文末提出了M(G)的关联色数猜想,其中M(G)为图G的Mycielski图．
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）.
出处
《数学进展》
CSCD
北大核心
2006年第2期171-177,共7页
Advances in Mathematics（China）
关键词
关联着色
关联色数
MYCIELSKI图
猜想
incidence coloring
incidence coloring number
Mycielski graphs
conjecture
