Multipass greedy coloring of simple uniform hypergraphs

DOI10.1002/rsa.20613zbMath1330.05071arXiv1310.5984MaRDI QIDQ3467582

Jakub Kozik

Publication date: 3 February 2016

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

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

zbMATH Keywords

greedy algorithm; hypergraph coloring; van der Waerden numbers

Mathematics Subject Classification ID

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

Related Items

Extremal problems for colorings of simple hypergraphs and applications, Improved algorithms for colorings of simple hypergraphs and applications, Colorings of \(b\)-simple hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Van der Waerden function and colorings of hypergraphs with large girth
• A remark concerning arithmetic progressions
• Greedy colorings of uniform hypergraphs
• Coloring uniform hypergraphs with few edges
• The Erdős-Hajnal problem of hypergraph colouring, its generalizations, and related problems
• Random coloring method in the combinatorial problem of Erdős and Lovász
• An application of Lovász' local lemma-A new lower bound for the van der Waerden number
• A note on random greedy coloring of uniform hypergraphs
• A Construction for Partitions Which Avoid Long Arithmetic Progressions
• On a property of families of sets
• On a combinatorial problem. II
• A new proof of Szemerédi's theorem