Article ID Journal Published Year Pages File Type
436663 Theoretical Computer Science 2014 9 Pages PDF
Abstract

A k-total-coloring of a graph G is a coloring of V(G)∪E(G) using k colors such that no two adjacent or incident elements receive the same color. A graph G is k-total-colorable if it admits a k-total-coloring. In this paper, it is proved that any graph G which can be embedded in a surface Σ of Euler characteristic χ(Σ)⩾0 is (Δ(G)+2)-total-colorable if Δ(G)⩾7, where Δ(G) denotes the maximum degree of G.

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