Name
Abstract | ||
|---|---|---|
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 Gn,p. We show that with high probability, the game chromatic number of Gn,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 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/rsa.v32:2 | Random Struct. Algorithms |
Keywords | Field | DocType |
bipartite graph,random graph | Wheel graph,Discrete mathematics,Edge coloring,Random regular graph,Combinatorics,Random graph,Graph power,Fractional coloring,Brooks' theorem,Critical graph,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 2 | 1042-9832 |
Citations | PageRank | References |
7 | 0.65 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tom Bohman | 1 | 250 | 33.01 |
| Alan M. Frieze | 2 | 4837 | 787.00 |
| Benny Sudakov | 3 | 1391 | 159.71 |