Tough Ramsey Graphs Without Short Cycles

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

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
Volume4
Issue number3
DOIs
StatePublished - Jan 1 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Discrete Mathematics and Combinatorics

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

Cite this