How to build a pillar: a proof of Thomassen's conjecture

DOI10.1016/J.JCTB.2023.04.004MaRDI QIDQ6170787zbMATH OpenFDO

Authors Irene Gil Fernández, Hong Liu

Publication date 10 August 2023

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.07777

zbMATH Keywords

pathsaverage degreecyclesexpander graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorial probability (60C05) Expander graphs (05C48)

Abstract: Carsten Thomassen in 1989 conjectured that if a graph has minimum degree more than the number of atoms in the universe ($delta(G)ge10^{10^{10}}$), then it contains a pillar, which is a graph that consists of two vertex-disjoint cycles of the same length, $s$ say, along with $s$ vertex-disjoint paths of the same length which connect matching vertices in order around the cycles. Despite the simplicity of the structure of pillars and various developments of powerful embedding methods for paths and cycles in the past three decades, this innocent looking conjecture has seen no progress to date. In this paper, we give a proof of this conjecture by building a pillar (algorithmically) in sublinear expanders.

Recommendations

• A note on Thomassen's conjecture
• On a conjecture of Thomassen concerning subgraphs of large girth
• A cycle of maximum order in a graph of high minimum degree has a chord
• Longest cycles and their chords
• Cycles of even lengths modulo \(k\)

Cites work

• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• A note on the Turán function of even cycles
• A proof of Mader's conjecture on large clique subdivisions in \(C_4\)-free graphs
• A solution to Erdős and Hajnal’s odd cycle problem
• A unified proof of conjectures on cycle lengths in graphs
• Clique immersion in graphs without a fixed bipartite graph
• Crux and Long Cycles in Graphs
• Cycles Modulo k
• Cycles of even length in graphs
• Dense graphs without 3-regular subgraphs
• Expanders -- how to find them, and what to find in them
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Extremal density for sparse minors and subdivisions
• Graph minors. XIII: The disjoint paths problem
• Highly linked graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Nested cycles with no geometric crossings
• On arithmetic progressions of cycle lengths in graphs
• On the maximal number of independent circuits in a graph
• Ramsey numbers of cycles versus general graphs
• The phase transition in random graphs: a simple proof
• Topological cliques in graphs II
• Vertex-disjoint cycles of the same length

Cited in

(6)

• Separating path systems of almost linear size
• Towards the Erdős-Gallai cycle decomposition conjecture
• Many Hamiltonian subsets in large graphs with given density
• Cycles with many chords
• Crux, space constraints and subdivisions
• Towards the Erdős-Gallai cycle decomposition conjecture

This page was built for publication: How to build a pillar: a proof of Thomassen's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170787)