The game chromatic number of random graphs
| dc.creator | Bohman, Tom | |
| dc.creator | Frieze, Alan | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-07-03 | |
| dc.date.accessioned | 2026-07-07T08:13:47Z | |
| dc.date.available | 2026-07-07T08:13:47Z | |
| dc.description | 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 paper 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. | |
| dc.identifier | https://arxiv.org/abs/0707.0465 | |
| dc.identifier | http://arxiv.org/abs/0707.0465 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132890 | |
| dc.subject | Combinatorics | |
| dc.title | The game chromatic number of random graphs | |
| dc.type | text |