On the chromatic number of a random hypergraph

DOI10.1016/j.jctb.2015.01.002zbMath1315.05051arXiv1208.0812OpenAlexW2088764637WikidataQ56323772 ScholiaQ56323772MaRDI QIDQ2347844

Catherine Greenhill, Alan M. Frieze, Martin Dyer

Publication date: 10 June 2015

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

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

zbMATH Keywords

hypergraphcolouringuniform hypergraphchromatic numberrandom hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65) Coloring of graphs and hypergraphs (05C15)

Related Items (26)

Waiter-client and client-waiter colourability and \(k\)-SAT games ⋮ On the strong chromatic number of random hypergraphs ⋮ Information-theoretic thresholds from the cavity method ⋮ On the \(s\)-colorful number of a random hypergraph ⋮ On the concentration of the chromatic number of a random hypergraph ⋮ On Two Limit Values of the Chromatic Number of a Random Hypergraph ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Panchromatic 3-coloring of a random hypergraph ⋮ Panchromatic 3-colorings of random hypergraphs ⋮ On the concentration of values of \(j\)-chromatic numbers of random hypergraphs ⋮ Bounds on threshold probabilities for coloring properties of random hypergraphs ⋮ Phase transitions in theq-coloring of random hypergraphs ⋮ Estimating the strong \(r\)-colorability threshold in random hypergraphs ⋮ On panchromatic colourings of a random hypergraph ⋮ On the strong chromatic number of a random 3-uniform hypergraph ⋮ On the chromatic numbers of random hypergraphs ⋮ Charting the replica symmetric phase ⋮ Panchromatic colorings of random hypergraphs ⋮ The satisfiability threshold for random linear equations ⋮ On the Potts antiferromagnet on random graphs ⋮ Equitable colorings of hypergraphs with few edges ⋮ On the weak chromatic number of random hypergraphs ⋮ Rigid Colorings of Hypergraphs and Contiguity ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ New lower bound for the minimal number of edges of simple uniform hypergraph without the property \(B_k\) ⋮ Model-based clustering for random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper-bounding the \(k\)-colorability threshold by counting covers
• The first cycles in an evolving graph
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• Two‐coloring random hypergraphs
• Constrained Critical Points
• On the Number of Perfect Matchings in Random Lifts
• The condensation transition in random hypergraph 2-coloring

This page was built for publication: On the chromatic number of a random hypergraph