Relaxed very asymmetric coloring games

This paper investigates a competitive version of the coloring game on a finite graph G. An asymmetric variant of the (r,d)-relaxed coloring game is called the (r,d)-relaxed (a,b)-coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph G, using colors from a set X, with |X|=r. On each turn Alice colors a vertices and Bob colors b vertices. A color α∈X is legal for an uncolored vertex u if by coloring u with color α, the subgraph induced by all the vertices colored with α has maximum degree at most d. Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The d-relaxed (a,b)-game chromatic number, denoted by , of G is the least r for which Alice has a winning strategy in the (r,d)-relaxed (a,b)-coloring game.The (r,d)-relaxed (1,1)-coloring game has been well studied and there are many interesting results. For the (r,d)-relaxed (a,1)-coloring game, this paper proves that if a graph G has an orientation with maximum outdegree k and a≥k, then for all d≥k²+2k; If a≥k³, then (a,1)- for all d≥2k+1.     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Game-perfect digraphs

In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The players move alternately, where a move of Bob consists in coloring a vertex, and a move of Alice in coloring a vertex or missing the turn. The game ends when Bob is unable to move. Alice wins if every vertex is colored at the end, otherwise Bob wins. This game is a variant of a graph coloring game proposed by Bodlaender (Int J Found Comput Sci 2:133?C147, 1991). The A-game chromatic number of D is the smallest cardinality of a color set C, so that Alice has a winning strategy for the game played on D with C. A digraph is A-perfect if, for any induced subdigraph H of D, the A-game chromatic number of H equals the size of the largest symmetric clique of H. We characterize some basic classes of A-perfect digraphs, in particular all A-perfect semiorientations of paths and cycles. This gives us, as corollaries, similar results for other games, in particular concerning the digraph version of the usual game chromatic number.     

Weak acyclic coloring and asymmetric coloring games

We introduce the notion of weak acyclic coloring of a graph. This is a relaxation of the usual notion of acyclic coloring which is often sufficient for applications. We then use this concept to analyze the (a,b)-coloring game. This game is played on a finite graph G, using a set of colors X, by two players Alice and Bob with Alice playing first. On each turn Alice (Bob) chooses a (b) uncolored vertices and properly colors them with colors from X. Alice wins if the players eventually create a proper coloring of G; otherwise Bob wins when one of the players has no legal move. The (a,b)-game chromatic number of G, denoted (a,b)-χ_g(G), is the least integer t such that Alice has a winning strategy when the game is played on G using t colors. We show that if the weak acyclic chromatic number of G is at most k then (2,1)-.     

Complete Multipartite Graphs and the Relaxed Coloring Game

Let k be a positive integer, d be a nonnegative integer, and G be a finite graph. Two players, Alice and Bob, play a game on G by coloring the uncolored vertices with colors from a set X of k colors. At all times, the subgraph induced by a color class must have maximum degree at most d. Alice wins the game if all vertices are eventually colored; otherwise, Bob wins. The least k such that Alice has a winning strategy is called the d-relaxed game chromatic number of G, denoted ?? _g ^d (G). It is known that there exist graphs such that ?? _g ⁰(G)?=?3, but ?? _g ¹(G)?>?3. We will show that for all positive integers m, there exists a complete multipartite graph G such that m?????? _g ⁰(G)?<??? _g ¹(G).     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Asymmetric graph coloring games

We introduce the (a,b)‐coloring game, an asymmetric version of the coloring game played by two players Alice and Bob on a finite graph, which differs from the standard version in that, in each turn, Alice colors a vertices and Bob colors b vertices. We also introduce a related game, the (a,b)‐marking game. We analyze these games and determine the (a,b)‐chromatic numbers and (a,b)‐coloring numbers for the class of forests and all values of a and b. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 169–185, 2005     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

The 6-relaxed game chromatic number of outerplanar graphs

Suppose G is a graph and k,d are integers. The (k,d)-relaxed colouring game on G is a game played by two players, Alice and Bob, who take turns colouring the vertices of G with legal colours from a set X of k colours. Here a colour i is legal for an uncoloured vertex x if after colouring x with colour i, the subgraph induced by vertices of colour i has maximum degree at most d. Alice’s goal is to have all the vertices coloured, and Bob’s goal is the opposite: to have an uncoloured vertex without a legal colour. The d-relaxed game chromatic number of G, denoted by , is the least number k so that when playing the (k,d)-relaxed colouring game on G, Alice has a winning strategy. This paper proves that if G is an outerplanar graph, then for d≥6.     

Very Asymmetric Marking Games

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.     

The game chromatic number of random graphs

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number χ_g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph G_n,p. We show that with high probability, the game chromatic number of G_n,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Directed defective asymmetric graph coloring games

We consider the following 2-person game which is played with an (initially uncolored) digraph D, a finite color set C, and nonnegative integers a, b, and d. Alternately, player I colors a vertices and player II colors b vertices with colors from C. Whenever a player colors a vertex v, all in-arcs (w,v) that do not come from a vertex w previously colored with the same color as v are deleted. For each color i the defect digraphD_i is the digraph induced by the vertices of color i at a certain state of the game. The main rule the players have to respect is that at every time for any color i the digraph D_i has maximum total degree of at most d. The game ends if no vertex can be colored any more according to this rule. Player I wins if D is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called . This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound (resp., ) for the d-relaxed (a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any d and a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a<b.     

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

Acyclic edge chromatic number of outerplanar graphs

A proper edge coloring of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by χ(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using χ(G) colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 22–36, 2010     

外平面图的有界染色

图G的k-有界染色是图G的一个最多有k个顶点染同一种颜色的顶点染色．图 G的k-有界染色数Xk(G)是指对G进行k-有界染色用的最少颜色数．本文给出了n个顶点的外平面图能用[n/k]种颜色k-有界染色的一些充分条件．     

Precoloring extension for K4‐minor‐free graphs

Let G=(V, E) be a graph where every vertex v∈V is assigned a list of available colors L(v). We say that G is list colorable for a given list assignment if we can color every vertex using its list such that adjacent vertices get different colors. If L(v)={1, …, k} for all v∈V then a corresponding list coloring is nothing other than an ordinary k‐coloring of G. Assume that W?V is a subset of V such that G[W] is bipartite and each component of G[W] is precolored with two colors taken from a set of four. The minimum distance between the components of G[W] is denoted by d(W). We will show that if G is K₄‐minor‐free and d(W)≥7, then such a precoloring of W can be extended to a 4‐coloring of all of V. This result clarifies a question posed in 10. Moreover, we will show that such a precoloring is extendable to a list coloring of G for outerplanar graphs, provided that |L(v)|=4 for all v∈V\W and d(W)≥7. In both cases the bound for d(W) is best possible. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 284‐294, 2009     

Circular game chromatic number of graphs

In a circular r-colouring game on G, Alice and Bob take turns colouring the vertices of G with colours from the circle S(r) of perimeter r. Colours assigned to adjacent vertices need to have distance at least 1 in S(r). Alice wins the game if all vertices are coloured, and Bob wins the game if some uncoloured vertices have no legal colour. The circular game chromatic number χ_cg(G) of G is the infimum of those real numbers r for which Alice has a winning strategy in the circular r-colouring game on G. This paper proves that for any graph G, , where is the game colouring number of G. This upper bound is shown to be sharp for forests. It is also shown that for any graph G, χ_cg(G)≤2χ_a(G)(χ_a(G)+1), where χ_a(G) is the acyclic chromatic number of G. We also determine the exact value of the circular game chromatic number of some special graphs, including complete graphs, paths, and cycles.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

List total colorings of series-parallel graphs

A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition.