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.     

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     

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.     

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)-.     

The relaxed game chromatic number of outerplanar graphs

The (r,d)‐relaxed coloring game is played by two players, Alice and Bob, on a graph G with a set of r colors. The players take turns coloring uncolored vertices with legal colors. A color α is legal for an uncolored vertex u if u is adjacent to at most d vertices that have already been colored with α, and every neighbor of u that has already been colored with α is adjacent to at most d – 1 vertices that have already been colored with α. Alice wins the game if eventually all the vertices are legally colored; otherwise, Bob wins the game when there comes a time when there is no legal move left. We show that if G is outerplanar then Alice can win the (2,8)‐relaxed coloring game on G. It is known that there exists an outerplanar graph G such that Bob can win the (2,4)‐relaxed coloring game on G. © 2004 Wiley Periodicals, Inc. J Graph Theory 46:69–78, 2004     

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.     

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).     

Clique coloring of binomial random graphs

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.     

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     

A characterization of triangle-free tolerance graphs

We prove that a triangle-free graph G is a tolerance graph if and only if there exists a set of consecutively ordered stars that partition the edges of G. Since tolerance graphs are weakly chordal, a tolerance graph is bipartite if and only if it is triangle-free. We, therefore, characterize those tolerance graphs that are also bipartite. We use this result to show that in general, the class of interval bigraphs properly contains tolerance graphs that are triangle-free (and hence bipartite).     

Acyclic vertex coloring of graphs of maximum degree 5

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a(G), is the minimum number of colors required for acyclic vertex coloring of graph G. For a family F of graphs, the acyclic chromatic number of F, denoted by a(F), is defined as the maximum a(G) over all the graphs G∈F. In this paper we show that a(F)=8 where F is the family of graphs of maximum degree 5 and give a linear time algorithm to achieve this bound.     

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.     

On the Acyclic Chromatic Number of Hamming Graphs

An acyclic coloring of a graph G is a proper coloring of the vertex set of G such that G contains no bichromatic cycles. The acyclic chromatic number of a graph G is the minimum number k such that G has an acyclic coloring with k colors. In this paper, acyclic colorings of Hamming graphs, products of complete graphs, are considered. Upper and lower bounds on the acyclic chromatic number of Hamming graphs are given. Gretchen L. Matthews: The work of this author is supported by NSA H-98230-06-1-0008.     

Some results on the incidence coloring number of a graph

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G², we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1.     

Lambda-fold 2-perfect 6-cycle systems in equipartite graphs

A 6-cycle system of a graph G is an edge-disjoint decomposition of G into 6-cycles. Graphs G, for which necessary and sufficient conditions for existence of a 6-cycle system have been found, include complete graphs and complete equipartite graphs. A 6-cycle system of G is said to be 2-perfect if the graph formed by joining all vertices distance 2 apart in the 6-cycles is again an edge-disjoint decomposition of G, this time into 3-cycles, since the distance 2 graph in any 6-cycle is a pair of disjoint 3-cycles.Necessary and sufficient conditions for existence of 2-perfect 6-cycle systems of both complete graphs and complete equipartite graphs are known, and also of λ-fold complete graphs. In this paper, we complete the problem, giving necessary and sufficient conditions for existence of λ-fold 2-perfect 6-cycle systems of complete equipartite graphs.     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010