首页 | 本学科首页   官方微博 | 高级检索  
     


Linear coloring of planar graphs with large girth
Authors:André   Raspaud
Affiliation:LaBRI UMR CNRS 5800, Universite Bordeaux I, 33405 Talence Cedex, France
Abstract:A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic numberView the MathML source of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has View the MathML source if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.
Keywords:Planar graph   Linear coloring   Girth   Maximum degree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号