Grünbaum's conjecture on the existence of k-chromatic graphs of degree k and girth g for every k ≥ 3, g ≥ 3 is disproved. In particular, the bound obtained states that the chromatic number of a triangle-free graph does not exceed [ 3(σ + 2) 4], where σ is the graph's degree.
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics