Improved algorithms for colorings of simple hypergraphs and applications

DOI10.1016/j.jctb.2015.09.004zbMath1327.05113arXiv1409.6921MaRDI QIDQ896005

Dmitriy A. Shabanov, Jakub Kozik

Publication date: 11 December 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

colorings of hypergraphs; sparse hypergraphs; random recoloring method; van der Waerden number

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C65: Hypergraphs

05C15: Coloring of graphs and hypergraphs

05C07: Vertex degrees

Cites Work

• Unnamed Item
• Unnamed Item
• A remark concerning arithmetic progressions
• On the chromatic number of set systems
• Coloring uniform hypergraphs with few edges
• Coloring H-free hypergraphs
• Constructions of sparse uniform hypergraphs with high chromatic number
• 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
• Multipass greedy coloring of simple uniform hypergraphs
• Colourings of Uniform Hypergraphs with Large Girth and Applications
• A Construction for Partitions Which Avoid Long Arithmetic Progressions