Game chromatic number of Cartesian product graphs
The electronic journal of combinatorics, Tome 15 (2008)
The game chromatic number $\chi _{g}$ is considered for the Cartesian product $G\,\square \,H$ of two graphs $G$ and $H$. Exact values of $\chi _{g}(K_2\square H)$ are determined when $H$ is a path, a cycle, or a complete graph. By using a newly introduced "game of combinations" we show that the game chromatic number is not bounded in the class of Cartesian products of two complete bipartite graphs. This result implies that the game chromatic number $\chi_{g}(G\square H)$ is not bounded from above by a function of game chromatic numbers of graphs $G$ and $H$. An analogous result is derived for the game coloring number of the Cartesian product of graphs.
@article{10_37236_796,
author = {T. Bartnicki and B. Bre\v{s}ar and J. Grytczuk and M. Kov\v{s}e and Z. Miechowicz and I. Peterin},
title = {Game chromatic number of {Cartesian} product graphs},
journal = {The electronic journal of combinatorics},
year = {2008},
volume = {15},
doi = {10.37236/796},
zbl = {1178.05039},
url = {http://geodesic.mathdoc.fr/articles/10.37236/796/}
}
TY - JOUR AU - T. Bartnicki AU - B. Brešar AU - J. Grytczuk AU - M. Kovše AU - Z. Miechowicz AU - I. Peterin TI - Game chromatic number of Cartesian product graphs JO - The electronic journal of combinatorics PY - 2008 VL - 15 UR - http://geodesic.mathdoc.fr/articles/10.37236/796/ DO - 10.37236/796 ID - 10_37236_796 ER -
%0 Journal Article %A T. Bartnicki %A B. Brešar %A J. Grytczuk %A M. Kovše %A Z. Miechowicz %A I. Peterin %T Game chromatic number of Cartesian product graphs %J The electronic journal of combinatorics %D 2008 %V 15 %U http://geodesic.mathdoc.fr/articles/10.37236/796/ %R 10.37236/796 %F 10_37236_796
T. Bartnicki; B. Brešar; J. Grytczuk; M. Kovše; Z. Miechowicz; I. Peterin. Game chromatic number of Cartesian product graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/796
Cité par Sources :