Every Graph of Sufficiently Large Average Degree Contains a C ₄-Free Subgraph of Large Average Degree

We prove that for every k there exists d=d(k) such that every graph of average degree at least d contains a subgraph of average degree at least k and girth at least six. This settles a special case of a conjecture of Thomassen.

Similar content being viewed by others

C₄-free subgraphs with large average degree

Article 25 November 2021

Induced Subgraphs of Induced Subgraphs of Large Chromatic Number

Article Open access 25 September 2023

Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

Article 28 November 2016

Author information

Authors and Affiliations

1. Freie Universität Berlin, Institut für Mathematik, Arnimallee 3, 14195, Berlin, Germany

   Daniela Kühn

2. Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099, Berlin, Germany

   Deryk Osthus

Authors

1. Daniela Kühn
   View author publications

   You can also search for this author in PubMed Google Scholar

2. Deryk Osthus
   View author publications

   You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Daniela Kühn.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kühn, D., Osthus, D. Every Graph of Sufficiently Large Average Degree Contains a C ₄-Free Subgraph of Large Average Degree. Combinatorica 24, 155–162 (2004). https://doi.org/10.1007/s00493-004-0010-2

Download citation

• Received: 14 June 2000

• Issue Date: January 2004

• DOI: https://doi.org/10.1007/s00493-004-0010-2

Mathematics Subject Classification (2000):

• 05C35
• 05D40