Abstract
We prove that for every connected 4-colourable graph G of order n and minimum degree δ ≥ 1, diam (G) ≤ frac(5 n, 2 δ) - 1. This is a first step toward proving a conjecture of Erdo{double acute}s, Pach, Pollack and Tuza [P. Erdo{double acute}s, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 279-285] from 1989. Our bound is tight since a family of graphs constructed in the above-cited reference has diameter frac(5 n, 2 δ) - 5.
Original language | English |
---|---|
Pages (from-to) | 1082-1089 |
Number of pages | 8 |
Journal | European Journal of Combinatorics |
Volume | 30 |
Issue number | 5 |
DOIs | |
Publication status | Published - Jul 2009 |
Externally published | Yes |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics