Very Asymmetric Marking Games |
| |
Authors: | Email author" target="_blank">H?A?KiersteadEmail author Daqing?Yang |
| |
Institution: | (1) Department of Mathematics and Statistics, Arizona State University, Tempe, AZ 85287-1804, USA |
| |
Abstract: | We investigate a competitive version of the coloring number of a graph G = (V, E). For a fixed linear ordering L of V let s (L) be one more than the maximum outdegree of G when G is oriented so that x ← y if x <
L
y. The coloring number of G is the minimum of s (L) over all such orderings. The (a, b)-marking game is played on a graph G = (V, E) as follows. At the start all vertices are unmarked. The players, Alice and Bob, take turns playing. A play consists of Alice
marking a unmarked vertices or Bob marking b unmarked vertices. The game ends when there are no remaining unmarked vertices. Together the players create a linear ordering
L of V defined by x < y if x is marked before y. The score of the game is s (L). The (a, b)-game coloring number of G is the minimum score that Alice can obtain regardless of Bob’s strategy. The usual (1, 1)-marking game is well studied and
there are many interesting results. Our main result is that if G has an orientation with maximum outdegree k then the (k, 1)-game coloring number of G is at most 2k + 2. This extends a fundamental result on the (1, 1)-game coloring number of trees. We also construct examples to show that
this bound is tight for many classes of graphs. Finally we prove bounds on the (a, 1)-game coloring number when a < k. |
| |
Keywords: | 05C15 05C20 |
本文献已被 SpringerLink 等数据库收录! |
|