平面图的线性着色  

Linear Coloring of Planar Graphs

作　　者：彩春丽[1] 谢德政[1] 

机构地区：[1]重庆大学数学与统计学院,重庆401331

出　　处：《西南大学学报（自然科学版）》2013年第2期99-102,共4页Journal of Southwest University(Natural Science Edition)

基　　金：重庆市科委自然科学基金计划资助项目(CSTC;2007BB2123)

摘　　要：研究了平面图的线性着色.对平面图G,证明了lc(G)≤min{2Δ(G)+3,Δ(G)+15}和lc(G)≤max{└0.9Δ(G)┘+4,┌Δ(G)/2┐+22},改进了平面图线性着色色数的上界.The linear coloring of planar graphs is studied in this paper. For a planar graph G, it is proved thatlc（G）≤min{2△（G）＋3, △（G）＋15} andlc（G）≤max{ └0.9A（G） ┘ ＋4,└△（G）/2┘ ＋22}, thus improving the upper bounds on the linear chromatic number of planar graphs.

关 键 词：平面图 线性着色 线性色数 最大度 

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