Asymmetric directed graph coloring games |
| |
Authors: | Stephan Dominique Andres |
| |
Affiliation: | Zentrum für angewandte Informatik Köln, University of Cologne, Weyertal 80, 50931 Köln, Germany |
| |
Abstract: | This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth. |
| |
Keywords: | Game chromatic number Game coloring number Forest Directed graph coloring game Outerplanar graph Surface Girth |
本文献已被 ScienceDirect 等数据库收录! |
|