图与其Mycielski图关联色数的关系(英文)  

The Relationship Between a Graph's Incidence Coloring Number and Its Mycielski Graph's Incidence Coloring Number

作　　者：张丽[1] 陈东灵[1] 陈学刚[1] 

机构地区：[1]山东科技大学信息科学与工程学院,青岛山东266510

出　　处：《数学进展》2006年第2期171-177,共7页Advances in Mathematics（China）

摘　　要：本文证明了对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）.

关 键 词：关联着色 关联色数 MYCIELSKI图 猜想 

分 类 号：O157.5[理学—数学]