On the additive chromatic number of several families of graphs
Preprint
Abstract
The Additive Coloring Problem is a variation of the Coloring Problem where labels of $\{1,\ldots,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 \emph{additive chromatic number} of $G$. This problem was first presented by Czerwi\'nski, Grytczuk and \.Zelazny 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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Additive list coloring of planar graphs with given girthDiscussiones Mathematicae Graph Theory, 2020
- Topological additive numbering of directed acyclic graphsInformation Processing Letters, 2015
- Computation of lucky number of planar graphs is NP-hardInformation Processing Letters, 2012
- Lucky labelings of graphsInformation Processing Letters, 2009