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

DOI10.1016/J.DISC.2015.05.020MaRDI QIDQ2515567zbMATH OpenOpenAlexFDO

Authors Jonathan Rollin, Maria Axenovich

Publication date 5 August 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.1219

zbMATH Keywords

\(\{1, t \}\)-factorscoloringconflict-freefactorsunique color

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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,Delta)$ be the smallest integer $k$ such that each $r$-uniform hypergraph of maximum vertex degree $Delta$ 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,Delta)leqDelta+1$. Compared to Brooks' theorem, according to which there is only a couple of graphs/hypergraphs that attain the $Delta+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,Delta)$ in terms of~$Delta$ for large~$Delta$ 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<fracr3$.

Recommendations

• Conflict-free colourings of uniform hypergraphs with few edges
• Conflict-free colourings of graphs and hypergraphs
• On variants of conflict-free-coloring for hypergraphs
• Conflict-free colouring of graphs
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs

Cites work

• \(\{k,r-k\}\)-factors of \(r\)-regular graphs
• Conflict-free coloring and its applications
• Conflict-free coloring of points and simple regions in the plane
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free colouring of graphs
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free colourings of uniform hypergraphs with few edges
• Factors and factorizations of graphs. Proof techniques in factor theory
• Graph unique-maximum and conflict-free colorings
• scientific article; zbMATH DE number 2209737 (Why is no real title available?)
• Note on parity factors of regular graphs
• On an edge ranking problem of trees and graphs
• On The Chromatic Number of Geometric Hypergraphs
• On the existence of general factors in regular graphs
• Optimal edge ranking of trees in linear time
• Rankings of Graphs
• The colour theorems of Brooks and Gallai extended
• Unique-maximum and conflict-free coloring for hypergraphs and tree graphs
• Zero-sum magic labelings and null sets of regular graphs

Cited in

(5)

• Regular colorings in regular graphs
• A result on fractional \((a,b,k)\)-critical covered graphs
• Degree conditions for fractional \((a,b,k)\)-critical covered graphs
• Conflict-free colourings of uniform hypergraphs with few edges
• Brooks-type theorems for relaxations of square colorings

This page was built for publication: Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2515567)