Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646636 | Discrete Mathematics | 2016 | 15 Pages |
Abstract
It is shown that for any fixed c≥3c≥3 and rr, the maximum possible chromatic number of a graph on nn vertices in which every subgraph of radius at most rr is cc-colorable is Θ̃(n1r+1): it is O((n/logn)1r+1) and Ω(n1r+1/logn). The proof is based on a careful analysis of the local and global colorability of random graphs and implies, in particular, that a random nn-vertex graph with the right edge probability has typically a chromatic number as above and yet most balls of radius rr in it are 2-degenerate.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Noga Alon, Omri Ben-Eliezer,