IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Diameter of 3-colorable graphs

  • Jan. 24, 2020
  • 2:30 p.m.


The problem of bounding the diameter of a graph in terms of its order and minimum degree was solved by several authors independently between 1965–1989. They have proved that $\text{diam}(G)\leq \frac{3n}{\delta+1}+O(1)$ for a graph $G$ with a fixed minimum degree $\delta \geq 2$ and large order $n$. In 1989 Erdős, Pach, Pollack, and Tuza conjectured that this upper bound can be improved if $G$ does not contain a complete subgraph $K _ k$. There is no progress on the conjecture has been reported, even for a specific value of $k$. In 2008 Czabarka, Dankelmann, and Székely proved a weakening of the conjecture for $K _ 5$-free graphs. They proved that the conjecture holds under the stronger assumption that $G$ is 4-colorable. In this project, we found a counterexample for 3-colorable graphs, hence is automatically also a counterexample for the conjecture on the diameter of $K _ 4$-free graphs. We use linear programming approach in attempt to prove a different improvement for the diameter of 3-colorable graphs. Joint work with Éva Czabarka and László Székely.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster