Name
Abstract | ||
|---|---|---|
Let Gn,p denote the random graph on n labeled vertices, where each edge is included with probability p independent of the others. We show that for all constant pχ(Gn,p)≥n2log11−pn−2log11−plog11−pn−2log11−p2+o(1) holds with high probability. This improves the best known lower bound for the chromatic number of dense random graphs and shows in particular that the estimate χ(Gn,p)≥nα(Gn,p), where α denotes the independence number, is not tight. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.09.019 | Discrete Mathematics |
Keywords | DocType | Volume |
Random graphs,Chromatic number | Journal | 309 |
Issue | ISSN | Citations |
10 | 0012-365X | 2 |
PageRank | References | Authors |
0.38 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantinos Panagiotou | 1 | 290 | 27.80 |
| Angelika Steger | 2 | 995 | 111.50 |