On sparse graphs with dense long paths

P. Erdős, Ronald Graham, Endre Szemerédi

Type: Article

Publication Date: 1975-01-01

Citations: 88

DOI: https://doi.org/10.1016/0898-1221(75)90037-1

View Publication

Locations

Computers & Mathematics with Applications - View
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Long paths in sparse random graphs	1982	Béla Bollobás
+	On Graphs Which Contain All Sparse Graphs	1982	László Babai Fan Chung Paul Erdös Ronald Graham J. Spencer
+	On large induced trees and long induced paths in sparse random graphs	1992	W. C. Stephen Suen
+ PDF Chat	Small Dense Subgraphs of a Graph	2017	Tao Jiang Andrew Newman
+	Long paths and cycles in subgraphs of the cube	2010	Eoin Long
+	Longest cycles in sparse random digraphs	2011	Michael Krivelevich Eyal Lubetzky Benny Sudakov
+	Longest cycles in sparse random digraphs	2011	Michael Krivelevich Eyal Lubetzky Benny Sudakov
+	Hamiltonian and long paths in bipartite graphs with connectivity	2022	Zhiyong Gan Yanping Xu
+ PDF Chat	Small subgraphs with large average degree	2023	Oliver Janzer Benny Sudakov István Tomon
+ PDF Chat	Long Circuits and Large Euler Subgraphs	2014	Fedor V. Fomin Petr A. Golovach
+	Long Circuits and Large Euler Subgraphs	2013	Fedor V. Fomin Petr A. Golovach
+	Long Circuits and Large Euler Subgraphs	2013	Fedor V. Fomin Petr A. Golovach
+ PDF Chat	Long induced paths in sparse graphs and graphs with forbidden patterns	2024	J. Duron Louis Esperet Jean‐Florent Raymond
+	Long Cycles in Graphs with Moderate Connectivity	1990	H. A. Jung
+ PDF Chat	Small Subgraphs with Large Average Degree	2024	Oliver Janzer Benny Sudakov István Tomon
+	Long $A$-$B$-paths have the edge-Erd\H os-P\'osa property	2019	Matthias Heinlein Arthur Ulmer
+	Algorithms for dense graphs and networks	1991	Joseph Cheriyan Kurt Mehlhorn
+	Estimating the number of graphs containing very long induced paths.	2008	Steven K. Butler
+	New families of graphs without short cycles and large size	2010	E. Abajo C. Balbuena A. Diánez
+	The Maximum Number of Short Paths in a Halin Graph	2023	Huiqing Liu Shunhai He

Works That Cite This (26)

Action	Title	Year	Authors
+	Matrix rigidity	2000	Bruno Codenotti
+ PDF Chat	Minimum <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="d1e35" altimg="si42.svg"><mml:mi>k</mml:mi></mml:math>-critical bipartite graphs	2021	Sylwia Cichacz Karol Suchan
+	Paul Erdös (1913?1996)	1997	László Babai
+	Explicit expanders and the Ramanujan conjectures	1986	Alexander Lubotzky Ralph S. Phillips Peter Sarnak
+ PDF Chat	Explicit construction of linear sized tolerant networks	1988	Noga Alon Fan Chung
+	On depth-reduction and grates	1983	Georg Schnitger
+	Explicit Construction of Linear Sized Tolerant Networks	1988	Noga Alon Fan Chung
+ PDF Chat	Eigenvalue asymptotics for Schrödinger operators on sparse graphs	2015	Michel Bonnefont Sylvain Golénia Matthias Keller
+	A separator theorem for planar graphs	1977	Richard J. Lipton Robert E. Tarjan
+	One node fault tolerance for caterpillars and starlike trees	1995	Frank Harary Mohammed Khurrum

Works Cited by This (1)

Action	Title	Year	Authors
+	On random graphs. I.	2022	P. Erdős A. Rényi