Disjoint type graphs with no short odd cycles

2020/04/08 by Chris Lambie-Hanson, Chris Lambie‐Hanson, Lambie-Hanson, Chris
Computer Science · Mathematics · #Advanced Graph Theory Research #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Logic (math.LO) #math.LO

paper · pdf · doi:10.48550/arxiv.2004.04189

6 pages. Unpublished note

arxiv created 2020/04/08 · openalex publication_date 2020/04/08 · arxiv updated 2020/04/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note, we provide a proof of a technical result of Erdős and Hajnal about the existence of disjoint type graphs with no odd cycles. We also prove that this result is sharp in a certain sense.

Related

• A refinement of theorems on vertex-disjoint chorded cycles
• The confirmation of a conjecture on disjoint cycles in a graph
• Graphs without two vertex-disjoint S-cycles
• A spectral condition for odd cycles in graphs
• Strengthening theorems of Dirac and Erdős on disjoint cycles