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

DOI10.1016/J.JCTB.2023.04.004zbMATH Open1519.05143arXiv2201.07777MaRDI QIDQ6170787FDOQ6170787

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)

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.

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

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\)

zbMATH Keywords

pathsaverage degreecyclesexpander graphs

Mathematics Subject Classification ID

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

Cites Work

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

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)