On the additive chromatic number of several families of graphs

preprint2020arXivOpen access

Abstract

The Additive Coloring Problem is a variation of the Coloring Problem where labels of {1,…,k}\{1,\ldots,k\} are assigned to the vertices of a graph GG so that the sum of labels over the neighborhood of each vertex is a proper coloring of GG. The least value kk for which GG admits such labeling is called \emph{additive chromatic number} of GG. This problem was first presented by Czerwiński, Grytczuk and Żelazny who also proposed a conjecture that for every graph GG, 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.