On coloring graphs with locally small chromatic number |
| |
Authors: | H A Kierstead E Szemerédi W T Trotter Jr |
| |
Institution: | (1) Department of Mathematics and Statistics, University of South Carolina, 29208 Columbia, S. C., USA |
| |
Abstract: | In 1973, P. Erdös conjectured that for eachkε2, there exists a constantc k so that ifG is a graph onn vertices andG has no odd cycle with length less thanc k n 1/k , then the chromatic number ofG is at mostk+1. Constructions due to Lovász and Schriver show thatc k , if it exists, must be at least 1. In this paper we settle Erdös’ conjecture in the affirmative. We actually prove a stronger result which provides an upper bound on the chromatic number of a graph in which we have a bound on the chromatic number of subgraphs with small diameter. |
| |
Keywords: | 05 C 15 |
本文献已被 SpringerLink 等数据库收录! |
|