图的无圈染色  

Acyclic coloring of graphs

作　　者：魏立鹏[1] 何文杰[1] 黄大江[1] 吴文文[1] 

机构地区：[1]河北工业大学理学院应用数学研究所,天津300130

出　　处：《河北省科学院学报》2010年第4期4-8,共5页Journal of The Hebei Academy of Sciences

基　　金：国家自然科学基金资助项目(10871058)

摘　　要：我们证明最大度Δ≥5的图的无圈色数至多是a(G)≤L(Δ-1)2/2」,这个结果比目前公认的最小上界a(G)=Δ(0-1)/2要小。同时得出两个新的结论:对任意Δ=5的图G,有a(G)≤8;对任意Δ=6的图G,有a(G)≤12。Any graph with maximum degree Δ≥5 has acyclic chromatic number at most a（G）≤L（Δ-1）2/2」 is proved.This result is less than the best general upper bound a（G）≤Δ（Δ-1）/2.and two new conclvsions are drew as follows：a（G）≤8,if any graph of Δ=5;a（G）≤12,if any graph of Δ=6.

关 键 词：无圈染色 无圈色数 最大度 

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