Total Coloring of Block-Cactus Graphs

Abstract

In this paper, we present new results about the coloring of graphs. We generalize the notion of proper vertex-coloring, introducing the concept of range-coloring of order $k$. The relation between range-coloring of order $k$ and total coloring is presented: we show that for any graph $G$ that has a range-coloring of order $\mathrm{\Delta }(G)$ with $t$ colors, there is a total coloring of $G$ that uses $(t+1)$ colors. This result provides a framework to prove that some families of graphs satisfy the total coloring conjecture. We exemplify with the family of block-cactus graphs.