Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421252 | Discrete Applied Mathematics | 2011 | 9 Pages |
Abstract
The total chromatic number of a graph GG, denoted by χ″(G)χ″(G), is the minimum number of colors needed to color the vertices and edges of GG such that no two adjacent or incident elements get the same color. It is known that if a planar graph GG has maximum degree Δ≥9Δ≥9, then χ″(G)=Δ+1χ″(G)=Δ+1. In this paper, we prove that if GG is a planar graph with maximum degree 77, and for every vertex vv, there is an integer kv∈{3,4,5,6}kv∈{3,4,5,6} so that vv is not incident with any kvkv-cycle, then χ″(G)=8χ″(G)=8.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gerard Jennhwa Chang, Jianfeng Hou, Nicolas Roussel,