Competitive Colorings of Oriented Graphs
Competitive Colorings of Oriented Graphs
复制标题
DOI：
10.37236/1611
复制
发表时间：
2000-09
期刊：
影响因子：
--
通讯作者：
H. Kierstead;W. T. Trotter
中科院分区：
文献类型：
--
作者：
H. Kierstead;W. T. Trotter
Ne set ril和Sopena引入了面向游戏色数的概念，并开发了一种通用的参数边界技术。在本文中,我们把他们的技术和概念引入的几个作者在一系列的论文比赛彩色数字显示每一个正整数k, t这里存在一个整数,如果C是一个拓扑封闭类图和C k个顶点不包含一个完整的图,然后每当G是一个方向的图C,面向游戏彩色t G的数量最多。特别地，有向平面图具有有界的有向博弈色数。这回答了neset ril和Sopena提出的一个问题。我们还通过构造一组有向图来回答Ne set ril和Sopena提出的第二个问题，其中有向博弈色数是有界的，但扩展围棋数不是。
Ne set ril and Sopena introduced a concept of oriented game chromatic number and developed a general technique for bounding this parameter. In this paper, we combine their technique with concepts introduced by several authors in a series of papers on game chromatic number to show that for every positive integer k ,t here exists an integer t so that if C is a topologically closed class of graphs and C does not contain a complete graph on k vertices, then whenever G is an orientation of a graph from C, the oriented game chromatic number of G is at most t .I n particular, oriented planar graphs have bounded oriented game chromatic number. This answers a question raised by Ne set ril and Sopena. We also answer a second question raised by Ne set ril and Sopena by constructing a family of oriented graphs for which oriented game chromatic number is bounded but extended Go number is not.