Tough Ramsey graphs without short cycles

Alon, Noga

Journal of Algebraic Combinatorics, Tome 4 (1995) no. 3, pp. 189-195.

Résumé

Summary: 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 $t_0$ so that every $t_0$-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 $OHgr(m^{4/3})$ vertices, improving previously known explicit constructions by Erdös and by Chung, Cleve and Dagum.

Détail

Classification : 05C35,, 05C38,, 05C55,, 05C25
Mots-clés : eigenvalues, Ramsey graph, tough graph, girth, Cayley graph