Random coloring method in the combinatorial problem of Erdős and Lovász

DOI10.1002/rsa.20366zbMath1241.05104MaRDI QIDQ3119050

Dmitriy A. Shabanov

Publication date: 7 March 2012

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

Full work available at URL: https://doi.org/10.1002/rsa.20366

zbMATH Keywords

extremal set theory; chromatic number; maximum vertex degree; simple hypergraphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

05C07: Vertex degrees

Related Items

Colourings of Uniform Hypergraphs with Large Girth and Applications, Extremal problems in hypergraph colourings, Improved algorithms for colorings of simple hypergraphs and applications, Coloring hypergraphs with bounded cardinalities of edge intersections, A generalization of the Hajnal-Szemerédi theorem for uniform hypergraphs, Colorings of partial Steiner systems and their applications, Multipass greedy coloring of simple uniform hypergraphs

Cites Work

• Lower bounds in the combinatorial problem of Erdős and Lovász
• Improvement of the lower bound in the Erdös-Hajnal combinatorial problem
• On the chromatic number of finite systems of subsets
• Hypergraphs with high chromatic number
• On 3-chromatic hypergraphs
• Coloring n-sets red and blue
• On the chromatic number of set systems
• On the Problem of Erdős and Hajnal in the Case of List Colorings
• Coloring uniform hypergraphs with few edges
• Coloring H-free hypergraphs
• Constructions of sparse uniform hypergraphs with high chromatic number
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• Coloring uniform hypergraphs with few colors
• Improved bounds and algorithms for hypergraph 2-coloring
• On a property of families of sets
• On a combinatorial problem. II