Conflict‐free chromatic number versus conflict‐free chromatic index
Michał Dębski, Jakub Przybyło
Abstract
Abstract A vertex coloring of a given graph is conflict‐free if the closed neighborhood of every vertex contains a unique color (i.e., a color appearing only once in the neighborhood). The minimum number of colors in such a coloring is the conflict‐free chromatic number of , denoted . What is the maximum possible conflict‐free chromatic number of a graph with a given maximum degree ? Trivially, , but it is far from optimal—due to results of Glebov, Szabó, and Tardos, and of Bhyravarapu, Kalyanasundaram, and Mathew, the answer is known to be . We show that the answer to the same question in the class of line graphs is —it follows that the extremal value of the conflict‐free chromatic index among graphs with maximum degree is much smaller than the one for conflict‐free chromatic number. The same result for is also provided in the class of near regular graphs, that is, graphs with minimum degree .