On some simple degree conditions that guarantee the upper bound on the chromatic (choice) number of random graphs
✍ Scribed by Vu, Van H.
- Publisher
- John Wiley and Sons
- Year
- 1999
- Tongue
- English
- Weight
- 318 KB
- Volume
- 31
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
It is well known that almost every graph in the random space G(n, p) has chromatic number of order O(np/ log(np)), but it is not clear how we can recognize such graphs without eventually computing the chromatic numbers, which is NP-hard. The first goal of this article is to show that the above-mentioned upper bound on the chromatic number can be guaranteed by simple degree conditions, which are satisfied by G(n, p) almost surely for most values of p. It turns out that the same conditions imply a similar bound for the choice number of a graph.
The proof implies a polynomial coloring algorithm for the case p is not too small.