×

Planar graph coloring with an uncooperative partner. (English) Zbl 0809.05044

Given an undirected graph \(G\) and a set of colors \(C\), two players can play the following game. They alternately color an uncolored vertex \(v\) of \(G\) with a color from \(C\) that has not been given to a neighbor of \(v\). The first player wins the game when the entire graph has been colored; the second player wins if he can prevent this. The game chromatic number of a graph \(G\) is the minimum size of \(| C|\) such that the first player has a winning strategy.
The question whether planar graphs have bounded game chromatic number is resolved in this paper: it is shown that the game chromatic number of a planar graph is at most 33. More generally, there exists a function \(f: \mathbb{N}\to \mathbb{N}\), so that for each \(n\in \mathbb{N}\), if a graph does not contain a homeomorphic of \(K_ n\), then its game chromatic number is at most \(f(n)\). In particular, the game chromatic number of a game is bounded in terms of its genus. It is also shown that the game chromatic number of an outerplanar graph is at most 8, and lower bounds for the game chromatic number of these classes of graphs are given.
The proof of the main result is motivated by the concept of \(p\)- arrangeability, which was first introduced by Guantao and Schelp in a Ramsey theoretic setting.

MSC:

05C15 Coloring of graphs and hypergraphs
91A43 Games involving graphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erdös, On chromatic number of graphs and set systems, Acta Math. Sci. Hung. 17 pp 61– (1966) · Zbl 0151.33701 · doi:10.1007/BF02020444
[2] Galvin, A Ramsey-type theorem for traceable graphs, J. of Combinat. Theory, Series B 33 pp 7– (1982) · Zbl 0477.05048 · doi:10.1016/0095-8956(82)90053-3
[3] Graham, Ramsey Theory (1980)
[4] Gyárfás, Colloquia Mathematica Societatis János Bolyai 10, Infinite and Finite Sets pp 801– (1975)
[5] A. Gyárfás Problems from the world surrounding perfect graphs Zastowania Matematyki Applicationes Mathemacticae XIX 1985 413 441
[6] Gyárfás, On-line and first-fit coloring of graphs, J. Graph Theory 12 pp 217– (1988) · Zbl 0657.05026 · doi:10.1002/jgt.3190120212
[7] A. Gyárfás J. Lehel First-Fit and on-line chromatic number of families of graphs
[8] Gyárfás, Induced subtrees in graphs of large chromatic number, Discrete Math. 30 pp 235– (1980) · Zbl 0475.05027 · doi:10.1016/0012-365X(80)90230-7
[9] H. Kierstead S. Penrice Recent results on a conjecture of Gyárfás
[10] Kierstead, On-line coloring and recursive graph theory, SIAM J. Discrete Math. · Zbl 0930.03050
[11] Sumner, The Theory and Applications of Graphs pp 557– (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.