A note on random greedy coloring of uniform hypergraphs

DOI10.1002/rsa.20556zbMath1325.05121arXiv1310.1368OpenAlexW2963164233MaRDI QIDQ3452724

Danila Cherkashin, Jakub Kozik

Publication date: 13 November 2015

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

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

zbMATH Keywords

hypergraphgreedy algorithmcoloring

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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