Veröffentlichung

Titel:

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

AutorInnen:

Maria Axenovich
Jonathan Rollin

Kategorie:

Artikel in Zeitschriften

erschienen in:

Discrete Mathematics, Vol. 338, No. 12, pp. 2295-2301, 2015

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,Δ) be the smallest integer k such that each r-uniform hypergraph of maximum vertex degree Δ has a conflict-free coloring with at most k colors. As shown by Pach and Tardos, similarly to a classical Brooks’ type theorem for hypergraphs, f(r,Δ)≤Δ+1. Compared to Brooks’ theorem, according to which there is only a couple of graphs/hypergraphs that attain the Δ+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,Δ) in terms of Δ for large Δ 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 (2014) stating that there is a {t,r−t}-factor in every r-regular graph for odd r and any odd t<r/3.

Download:

arXiv

BibTeX-Eintrag:

@article{, author = {Maria Axenovich and Jonathan Rollin}, title = {Brooks type results for conflict-free colorings and \{a, b\}-factors in graphs}, journal = {Discrete Mathematics}, volume = {338}, number = {12}, pages = {2295--2301}, year = {2015}, }