Brooks type results for conflict-free colorings and {a,b}{a,b}-factors in graphs

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,Δ)f(r,Δ) be the smallest integer  kk such that each  rr-uniform hypergraph of maximum vertex degree  ΔΔ has a conflict-free coloring with at most  kk colors. As shown by Pach and Tardos, similarly to a classical Brooks’ type theorem for hypergraphs,  f(r,Δ)≤Δ+1f(r,Δ)≤Δ+1. Compared to Brooks’ theorem, according to which there is only a couple of graphs/hypergraphs that attain the  Δ+1Δ+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,Δ)f(r,Δ) in terms of  ΔΔ for large  ΔΔ and establish the connection between conflict-free colorings and so-called   {t,r−t}{t,r−t}-factors in  rr-regular graphs. Here, a  {t,r−t}{t,r−t}-factor is a factor in which each degree is either  tt or r−tr−t. Among others, we disprove a conjecture of Akbari and Kano (2014) stating that there is a  {t,r−t}{t,r−t}-factor in every  rr-regular graph for odd  rr and any odd  t