Diameter of 4-colorable graphs with given minimum degree
by
Éva Czabarka
Coauthors: Peter Dankelmann László A. Székely

In 1989, Erdös, Pach, Pollack, and Tuza conjectured the following:

Let r, d ≥ 2 be fixed integers and let G be a connected graph with n vertices and minimum degree d.
(i) If G is K_2r-free and d is a multiple of (r-1)(3r+2) then, for large n, then

diam(G) ≤ 2(r-1)(3r+2) (2r2-1)d n + O(1).

(ii) If G is K_2r+1-free and d is a multiple of 3r-1, then, for large n,

diam(G) ≤ 3r-1 rd n + O(1).

They also constructed graphs showing that, if the above bounds hold, then they are sharp, apart from an additive constant.

So far, no progress on the above conjecture, even for specific values of r, has been reported. We consider a slight weakening of the above conjecture for K₅-free graphs. We show that the conjecture holds for all d ≥ 1 under the somewhat stronger assumption that G is 4-colourable.

Date received: January 24, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cavi-51.