The game chromatic number of a random hypergraph

DOI10.1007/978-3-030-55857-4_6MaRDI QIDQ2232032zbMATH OpenOpenAlexFDO

Authors Debsoumya Chakraborti, Mihir Hasabnis, Alan Frieze

Publication date 4 October 2021

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

zbMATH Keywords

chromatic number\(k\)-uniform hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65) Games involving graphs (91A43)

Abstract: We consider the following game, played on a $k$-uniform hypergraph $H$. There are $q$ colors available and two players take it in turns to color vertices. A partial coloring is proper if no edge is mono-chromatic. One player, A, wishes to color all the vertices and the other player, B, wishes to prevent this. The {em game chromatic number} $ch{i}_g(H)$ is the minimum number of colors for which A has a winning strategy. We consider this in the context of a random $k$-uniform hypergraph and prove upper and lower bounds that hold w.h.p.

Recommendations

• The game chromatic number of random graphs
• scientific article; zbMATH DE number 4200245
• The game chromatic number of dense random graphs
• On the game chromatic number of sparse random graphs
• scientific article; zbMATH DE number 1354920

Cited in

(7)

• The eternal game chromatic number of random graphs
• Coloring number and on-line Ramsey theory for graphs and hypergraphs
• On the game chromatic number of sparse random graphs
• scientific article; zbMATH DE number 5670857 (Why is no real title available?)
• scientific article; zbMATH DE number 4014765 (Why is no real title available?)
• The game chromatic number of random graphs
• The game chromatic number of dense random graphs

This page was built for publication: The game chromatic number of a random hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232032)