Conflict-free chromatic number vs conflict-free chromatic index

Abstract

A vertex coloring of a given graph $G$ 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 $G$, denoted ${\chi }_{CF}(G)$. What is the maximum possible conflict-free chromatic number of a graph with a given maximum degree $\Delta$? Trivially, ${\chi }_{CF}(G)\le \chi (G)\le \Delta +1$, but it is far from optimal - due to results of Glebov, Szabó and Tardos, and of Bhyravarapu, Kalyanasundaram and Mathew, the answer in known to be $\Theta \left({\ln }^2\Delta \right)$. We show that the answer to the same question in the class of line graphs is $\Theta \left(\ln \Delta \right)$ - that is, the extremal value of the conflict-free chromatic index among graphs with maximum degree $\Delta$ is much smaller than the one for conflict-free chromatic number. The same result for ${\chi }_{CF}(G)$ is also provided in the class of near regular graphs, i.e. graphs with minimum degree $\delta \ge \alpha \Delta$.

10 pages

Cited by in corpus (1)

• Conflict-Free Coloring of Star-Free Graphs on Open Neighborhoods