On the additive chromatic number of several families of graphs

Abstract

The Additive Coloring Problem is a variation of the Coloring Problem where labels of {1,…,k} are assigned to the vertices of a graph G so that the sum of labels over the neighborhood of each vertex is a proper coloring of G. The least value k for which G admits such labeling is called additive chromatic number of G. This problem was first presented by Czerwiński, Grytczuk and Żelazny who also proposed a conjecture that for every graph G, the additive chromatic number never exceeds the classic chromatic number. Up to date, the conjecture has been proved for complete graphs, trees, non-3-colorable planar graphs with girth at least 13 and non-bipartite planar graphs with girth at least 26. In this work, we show that the conjecture holds for split graphs. We also present exact formulas for computing the additive chromatic number for some subfamilies of split graphs (complete split, headless spiders and complete sun), regular bipartite, complete multipartite, fan, windmill, circuit, wheel, cycle sun and wheel sun.