The Game Chromatic Number of a Random Hypergraph

Debsoumya Chakraborti, Alan Frieze () and Mihir Hasabnis
Additional contact information
Debsoumya Chakraborti: Carnegie Mellon University
Alan Frieze: Carnegie Mellon University
Mihir Hasabnis: Carnegie Mellon University

A chapter in Discrete Mathematics and Applications, 2020, pp 153-175 from Springer

Abstract: 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 game chromatic number χ 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.

Date: 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-55857-4_6

Ordering information: This item can be ordered from
http://www.springer.com/9783030558574

DOI: 10.1007/978-3-030-55857-4_6

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().