Tough Ramsey graphs without short cycles (Q1893953)

The toughness \(t(G)\) of a graph \(G\) is the largest real number \(t\) so that for every positive integer \(x\geq 2\) at least \(tx\) vertices of \(G\) must be deleted to obtain a subgraph with at least \(x\) components. A graph \(G\) is \(t\)-tough if \(t(G)\geq t\). This invariant was introduced by \textit{V. Chvátal} [Discrete Math. 5, 215-218 (1973; Zbl 0256.05122)] who conjectured the existence of an absolute constant \(t_0\) such that every \(t_0\)-tough graph is pancyclic. Here, the conjecture is shown false as the author proves, by explicit construction, that for every \(t\) and \(g\) there exists a \(t\)-tough graph of girth greater than \(g\). Bauer, van den Heuvel, and Schmeichel [\textit{D. Bauer}, \textit{J. van den Heuvel} and \textit{E. Schmeichel}, Toughness and triangle-free graphs, to appear] had already shown this latter result for \(g= 3\). Also, the author constructs triangle-free graphs with independence number \(m\) on \(\Omega(m^{4/3})\) vertices thus improving results of \textit{F. R. K. Chung}, \textit{R. Cleve} and \textit{P. Dagum} [J. Comb. Theory, Ser. B 57, No. 1, 150-155 (1993; Zbl 0769.05066)] and notes (added in proof) that he has improved this to \(\Omega(m^{3/2})\) in [Explicit Ramsey graphs and orthonormal labelings, Electr. J. Comb. 1, R12 (1994; Zbl 0814.05056)].