Tough Ramsey Graphs Without Short Cycles

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


A graph G is t-tough if any induced subgraph of it with x > 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs of girth strictly greater than g. This strengthens a recent result of Bauer, van den Heuvel and Schmeichel who proved the above for g = 3, and hence disproves in a strong sense a conjecture of Chvátal that there exists an absolute constant t0 so that every t0-tough graph is pancyclic. The proof is by an explicit construction based on the tight relationship between the spectral properties of a regular graph and its expansion properties. A similar technique provides a simple construction of triangle-free graphs with independence number m on Ω(m4/3) vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.

Original languageEnglish (US)
Pages (from-to)189-195
Number of pages7
JournalJournal of Algebraic Combinatorics: An International Journal
Issue number3
StatePublished - Jul 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Algebra and Number Theory


  • Cayley graph
  • Ramsey graph
  • eigenvalues
  • girth
  • tough graph


Dive into the research topics of 'Tough Ramsey Graphs Without Short Cycles'. Together they form a unique fingerprint.

Cite this