Abstract:

A total k-coloring of a graph G is acoloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number of G is the smallest integer k such that G has a total k-coloring. It is proved here that the total chromatic number of a planar graph G is Δ(G)+1 if (1) Δ≥5 and every vertex is incident with at most one cycle of length at most 5, or (2) Δ≥4, the girth g≥4 and every vertex is incident with at most one cycle of length at most 7.

Key words: planar graph; total coloring; cycle; total chromatic number