New Bounds for Proper h‐Conflict‐Free Colorings

ABSTRACT A proper ‐coloring of a graph is called ‐conflict‐free if every vertex has at least colors appearing exactly once in its neighborhood. Let denote the minimum such that such a coloring exists. We show that for every fixed , every graph of maximum degree satisfies . This expands on the work of Cho et al., and improves a recent result of Liu and Reed in the case . We conjecture that for every and every graph of maximum degree sufficiently large, the bound should hold, which would be tight. When the minimum degree of is sufficiently large, namely , we show that this upper bound can be further reduced to . This improves a recent bound from Kamyczura and Przybyło when .