Brooks Type Results for Conflict-Free Colorings and {a, b}-factors in graphs

Abstract

A vertex-coloring of a hypergraph is conflict-free, if each edge contains a vertex whose color is not repeated on any other vertex of that edge. Let $f(r,\hat{I}”)$ be the smallest integer $k$ such that each $r$-uniform hypergraph of maximum vertex degree $\hat{I}”$ has a conflict-free coloring with at most $k$ colors. As shown by Tardos and Pach, similarly to a classical Brooks' type theorem for hypergraphs, $f(r,\hat{I}”)\le \hat{I}”+1$. Compared to Brooks' theorem, according to which there is only a couple of graphs/hypergraphs that attain the $\hat{I}”+1$ bound, we show that there are several infinite classes of uniform hypergraphs for which the upper bound is attained. We provide bounds on $f(r,\hat{I}”)$ in terms of~$\hat{I}”$ for large~$\hat{I}”$ and establish the connection between conflict-free colorings and so-called $\{t,r-t\}$-factors in $r$-regular graphs. Here, a $\{t,r-t\}$-factor is a factor in which each degree is either $t$ or $r-t$. Among others, we disprove a conjecture of Akbari and Kano~[Graphs and Combinatorics 30(4):821--826, 2014] stating that there is a $\{t,r-t\}$-factor in every $r$-regular graph for odd $r$ and any odd $t<\frac{r}{3}$.

Fixed typos in statement of Theorem 7; 9 pages, 1 figure