On the strong chromatic number of random graphs
| dc.creator | Loh, Po-Shen | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-14 | |
| dc.date.accessioned | 2026-07-07T08:10:07Z | |
| dc.date.available | 2026-07-07T08:10:07Z | |
| dc.description | Let G be a graph with n vertices, and let k be an integer dividing n. G is said to be strongly k-colorable if for every partition of V(G) into disjoint sets V_1 \cup ... \cup V_r, all of size exactly k, there exists a proper vertex k-coloring of G with each color appearing exactly once in each V_i. In the case when k does not divide n, G is defined to be strongly k-colorable if the graph obtained by adding k \lceil n/k \rceil - n isolated vertices is strongly k-colorable. The strong chromatic number of G is the minimum k for which G is strongly k-colorable. In this paper, we study the behavior of this parameter for the random graph G(n, p). In the dense case when p >> n^{-1/3}, we prove that the strong chromatic number is a.s. concentrated on one value Δ+1, where Δis the maximum degree of the graph. We also obtain several weaker results for sparse random graphs. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/0706.2110 | |
| dc.identifier | http://arxiv.org/abs/0706.2110 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131741 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C15, 05C80, 60C05 | |
| dc.title | On the strong chromatic number of random graphs | |
| dc.type | text |