Minimum total coloring of planar graph

摘要

Graph coloring is an important tool in the study of optimization, computer science, network design, e.g., file transferring in a computer network, pattern matching, computation of Hessians matrix and so on. In this paper, we consider one important coloring, vertex coloring of a total graph, which is familiar to us by the name of "total coloring". Total coloring is a coloring of V ∪ E such that no two adjacent or incident elements receive the same color. In other words, total chromatic number of G is the minimum number of disjoint vertex independent sets covering a total graph of G. Here, let G be a planar graph with Δ ≥ 8. We proved that if for every vertex v ∈ V, there exists two integers i_v, j_v ∈ {3,4,5,6,7,8} such that v is not incident with intersecting i_v-cycles and j_v-cycles, then the vertex chromatic number of total graph of G is Δ + 1, i.e., the total chromatic number of G is Δ + 1.