Tough Ramsey graphs without short cycles
type: Item
instance of: scholarly article
title: Tough Ramsey graphs without short cycles
zbMATH Open document ID: 0826.05039
DOI: 10.1023/A:1022453926717
author: Noga Alon
published in: Journal of Algebraic Combinatorics
publication date: 1995-11-16T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 773833
zbMATH Keywords: Ramsey graphs
zbMATH Keywords: short cycles
zbMATH Keywords: toughness
zbMATH Keywords: independence number
reviewed by: R. C. Entringer
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Eigenvalues and expanders
cites work: Explicit construction of linear sized tolerant networks
cites work: \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
cites work: Random Cayley graphs and expanders
cites work: The probabilistic method
cites work: Toughness and triangle-free graphs
cites work: Q3852212
cites work: Tough graphs and Hamiltonian circuits.
cites work: A note on constructive lower bounds for the Ramsey numbers \(R(3, t)\)
cites work: Q3900124
cites work: Graph Theory and Probability
cites work: Graph Theory and Probability. II
cites work: On the construction of certain graphs
cites work: Q3880849
cites work: Ramanujan graphs
cites work: Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
cites work: Q4146667
cites work: A note on the independence number of triangle-free graphs
cites work: Asymptotic lower bounds for Ramsey functions
cites work: Explicit Concentrators from Generalized N-Gons
full work available at URL: a:1022453926717
OpenAlex ID: W1482486802
Recommended article: On cycle—Complete graph ramsey numbers
Recommended article: Hypergraph Ramsey numbers: tight cycles versus cliques
Recommended article: The Cycle-Complete Graph Ramsey Numbers
Recommended article: Ramsey numbers for cycles in graphs
Recommended article: Cycles Are Strongly Ramsey-Unsaturated
Recommended article: Anti-Ramsey problems for cycles
Recommended article: Ramsey numbers of cycles versus general graphs
Recommended article: Cycle-Complete Ramsey Numbers
Recommended article: Q4004437
Recommended article: Q4526625
description: scientific article; zbMATH DE number 773833