高度图的关联色数

The Incidence Chromatic Number of High Degree Graphs

为了解决强边着色猜想 ,1993年 ,Brualdi和Massey(DiscreteMath .(12 2 ) 5 1- 5 8)引入了关联着色概念 .陈东灵等[2 ] 证明了对于△ (G) =n- 2的图G ,inc(G) △ (G) + 2 ,其中n是G的阶数 .本文将进一步探讨在什么条件下 ,它的关联色数肯定是△ (G) + 1,又在什么条件下 ,肯定是△ (G) + 2 .

In 1993,Brualdi and Massey (Discrete Math.(122)51-58)introduced the concept of incidence coloring in order to solve the conjecture of strong edge coloring. Chen Dong-ling etc.proved that inc(G)≤△(G)+2 for the graphs of △(G)=n-2, where n is the order of G. In this paper,we further discuss that its incidence chromatic number must be △(G)+1 under some conditions,and △(G)+2 under some other conditions.