A note on random greedy coloring of uniform hypergraphs

DOI10.1002/RSA.20556zbMATH Open1325.05121arXiv1310.1368OpenAlexW2963164233MaRDI QIDQ3452724FDOQ3452724

Authors: Danila Cherkashin, Jakub Kozik 

Publication date: 13 November 2015

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: The smallest number of edges forming an n-uniform hypergraph which is not r-colorable is denoted by m(n,r). ErdH{o}s and Lov'{a}sz conjectured that m(n,2)= heta(n 2^n)$. The best known lower bound m(n,2)=Omega(sqrt(n/log(n)) 2^n) was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on analysis of random greedy coloring algorithm investigated by Pluh'ar in 2009. The proof method extends to the case of r-coloring, and we show that for any fixed r we have m(n,r)=Omega((n/log(n))^(1-1/r) r^n) improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n-uniform hypergraph that is not r-colorable.

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

Recommendations

• Greedy colorings of uniform hypergraphs
• Coloring uniform hypergraphs with few colors
• On \(r\)-chromatic hypergraphs
• Colorings of hypergraphs with large number of colors
• Random coloring method in the combinatorial problem of Erdős and Lovász

zbMATH Keywords

greedy algorithmhypergraphcoloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cites Work

• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Improved bounds and algorithms for hypergraph 2-coloring
• On a combinatorial problem. II
• On \(r\)-chromatic hypergraphs
• Greedy colorings of uniform hypergraphs
• Coloring uniform hypergraphs with few colors

Cited In (35)

• Coloring hypergraphs with bounded cardinalities of edge intersections
• Greedy colorings of uniform hypergraphs
• Random coloring method in the combinatorial problem of Erdős and Lovász
• On colorings of 3-homogeneous hypergraphs in 3 colors
• Random hypergraphs and property B
• Multipass greedy coloring of simple uniform hypergraphs
• On the chromatic index of random uniform hypergraphs
• The intersection spectrum of 3‐chromatic intersecting hypergraphs
• Colourings of uniform hypergraphs with large girth and applications
• Colorings of \(b\)-simple hypergraphs
• A quantitative Lovász criterion for Property B
• The Cayley isomorphism property for Cayley maps
• 2-colorings of hypergraphs with large girth
• Extremal problems in hypergraph colourings
• Coloring uniform hypergraphs with few colors
• List colorings of multipartite hypergraphs
• List Coloring with a Bounded Palette
• Trees in greedy colorings of hypergraphs
• Extremal problems for colorings of simple hypergraphs and applications
• Improved Bounds for Uniform Hypergraphs without Property B
• DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces
• On some generalizations of the property B problem of an \(n\)-uniform hypergraph
• Equitable colorings of hypergraphs with few edges
• Interview with Joel Spencer
• The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
• Improved algorithms for colorings of simple hypergraphs and applications
• 2-colorings of uniform hypergraphs
• Equitable colorings of hypergraphs with \(r\) colors
• The minimum number of edges in uniform hypergraphs with property O
• New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\)
• Coloring cross-intersecting families
• On the Erdős-Hajnal problem for 3-graphs
• Colorings of hypergraphs with large number of colors
• Colorings of hypergraphs with large number of colors
• A note on two-colorability of nonuniform hypergraphs

This page was built for publication: A note on random greedy coloring of uniform hypergraphs

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