On Brooks' Theorem for Sparse Graphs
- 1 June 1995
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 4 (2) , 97-132
- https://doi.org/10.1017/s0963548300001528
Abstract
Let G be a graph with maximum degree Δ(G). In this paper we prove that if the girth g(G) of G is greater than 4 then its chromatic number, χ(G), satisfies where o(l) goes to zero as Δ(G) goes to infinity. (Our logarithms are base e.) More generally, we prove the same bound for the list-chromatic (or choice) number: provided g(G) < 4.Keywords
This publication has 16 references indexed in Scilit:
- Sharp concentration of the chromatic number on random graphsG n, pCombinatorica, 1987
- On a Packing and Covering ProblemEuropean Journal of Combinatorics, 1985
- A Lower Bound for Heilbronn'S ProblemJournal of the London Mathematical Society, 1982
- A Dense Infinite Sidon SequenceEuropean Journal of Combinatorics, 1981
- A note on Ramsey numbersJournal of Combinatorial Theory, Series A, 1980
- Covering the vertex set of a graph with subgraphs of smaller degreeDiscrete Mathematics, 1978
- Chromatic number, girth and maximal degreeDiscrete Mathematics, 1978
- A bound on the chromatic number of a graphDiscrete Mathematics, 1978
- On an upper bound of a graph's chromatic number, depending on the graph's degree and densityJournal of Combinatorial Theory, Series B, 1977
- On colouring the nodes of a networkMathematical Proceedings of the Cambridge Philosophical Society, 1941