Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree

DOI10.1007/s00493-004-0010-2zbMath1047.05022OpenAlexW2042135415MaRDI QIDQ1882146

Deryk Osthus, Daniela Kühn

Publication date: 19 October 2004

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-004-0010-2

zbMATH Keywords

graphaverage degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (13)

\(C_4\)-free subgraphs with large average degree ⋮ On low tree-depth decompositions ⋮ Resolution of the Erdős–Sauer problem on regular subgraphs ⋮ Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree ⋮ Triangle-free subgraphs with large fractional chromatic number ⋮ Regular partitions of gentle graphs ⋮ A note on Thomassen's conjecture ⋮ Decomposing graphs into paths of fixed length ⋮ Four-cycles in graphs without a given even cycle ⋮ On a conjecture of Thomassen concerning subgraphs of large girth ⋮ Decompositions of highly connected graphs into paths of length 3 ⋮ Edge-decompositions of highly connected graphs into paths ⋮ Dense Induced Subgraphs of Dense Bipartite Graphs

This page was built for publication: Every graph of sufficiently large average degree contains a \(C_4\)-free subgraph of large average degree