Article ID Journal Published Year Pages File Type
434435 Theoretical Computer Science 2014 10 Pages PDF
Abstract

The total chromatic number of a graph G  , denoted by χ″(G)χ″(G), is the minimum number of colors needed to color the vertices and edges of G such that no two adjacent or incident elements get the same color. It is known that if a planar graph G   has maximum degree Δ⩾9Δ⩾9, then χ″(G)=Δ+1χ″(G)=Δ+1. In this paper, we prove that if G is a planar graph with maximum degree 8, and for every vertex v, v   is incident with at most d(v)−2⌊d(v)5⌋ triangles, then χ″(G)=9χ″(G)=9.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,