Name
Abstract | ||
|---|---|---|
Let G be a graph with n vertices, and let kbe an integer dividing n. G is said to be stronglyk-colourable if, for every partition of V(G) intodisjoint sets V1∪ ···∪ Vr, all of size exactly k,there exists a proper vertex k-colouring of G witheach colour appearing exactly once in eachVi. In the case when k does notdivide n, G is defined to be stronglyk-colourable if the graph obtained by addingk[n/k]-n isolated vertices is stronglyk-colourable. The strong chromatic number of G is theminimum k for which G is stronglyk-colourable. In this paper, we study the behaviour of thisparameter for the random graphGn,p. In the dense case whenp n1/3, we prove that the strongchromatic number is a.s. concentrated on one value Δ + 1,where Δ is the maximum degree of the graph. We also obtainseveral weaker results for sparse random graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1017/S0963548307008607 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
random graphgn,n vertex,g witheach colour,notdivide n,sparse random graph,dense case whenp n1,strongchromatic number,strong chromatic number,theminimum k,n isolated vertex,maximum degree,random graph | Discrete mathematics,Random regular graph,Wheel graph,Strongly regular graph,Combinatorics,Graph toughness,Bound graph,Graph power,Cycle graph,Windmill graph,Mathematics | Journal |
Volume | Issue | ISSN |
17 | 2 | 0963-5483 |
Citations | PageRank | References |
2 | 0.39 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Po-Shen Loh | 1 | 133 | 18.68 |
| Benny Sudakov | 2 | 1391 | 159.71 |