The game chromatic number of a random hypergraph

DOI10.1007/978-3-030-55857-4_6zbMATH Open1473.05203arXiv1902.03130OpenAlexW2996701530MaRDI QIDQ2232032FDOQ2232032

Authors: Debsoumya Chakraborti, Mihir Hasabnis, Alan Frieze 

Publication date: 4 October 2021

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.

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

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

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)

Cited In (7)

• On the game chromatic number of sparse random graphs
• Title not available (Why is that?)
• The eternal game chromatic number of random graphs
• The game chromatic number of random graphs
• The game chromatic number of dense random graphs
• Title not available (Why is that?)
• Coloring number and on-line Ramsey theory for graphs and hypergraphs

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)