Diameter of 4-colourable graphs

É Czabarka, P. Dankelmann, L. A. Székely

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


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 languageEnglish
Pages (from-to)1082-1089
Number of pages8
JournalEuropean Journal of Combinatorics
Issue number5
Publication statusPublished - Jul 2009
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Diameter of 4-colourable graphs'. Together they form a unique fingerprint.

Cite this