Article ID Journal Published Year Pages File Type
421252 Discrete Applied Mathematics 2011 9 Pages PDF
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
, , ,