首页 | 本学科首页   官方微博 | 高级检索  
     


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 ba, 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号