摘要
The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ'' (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ'' (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ''(G) = 9.
The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ″ （G）. It is shown that if a planar graph G has maximum degree Δ≥9, then χ″ （G） = Δ ＋ 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ″（G） = 9.
基金
supported by Natural Science Foundation of Shandong Province (Grant No. ZR2009AM009)
Scientific Research Foundation for the Excellent Middle-Aged and Youth Scientists of Shandong Province (Grant No. BS2012SF016)
National Natural Science Foundation of China (Grant Nos.11001055 and 11101243)
关键词
平面图
相交
全着色
最小数
颜色
顶点
色数
total coloring, planar graph, chordal 4-cycles, triangles
