Every longest circuit of a 3-connected, K_3,3-minor free graph has a chord

2007/11/30 by Etienne Birmelé, E. Birmelé · 1 citation
Mathematics · #math.CO

paper · pdf · doi:10.1002/jgt.20312

published as Journal of Graph Theory, 58 (4): 293-298, 2008 · accepted by Journal of Graph Theory

arxiv created 2008/03/31 · arxiv updated 2011/09/07

Abstract

Carsten Thomassen conjectured that every longest circuit in a 3-connected graph has a chord. We prove the conjecture for graphs having no K_3,3 minor, and consequently for planar graphs.

Cited by

• Chords of longest cycles in graphs with large circumferences

Related

• Chords of longest circuits of graphs embedded in torus and Klein bottle
• Longest cycles and their chords
• A conjecture implying Thomassen's chord conjecture in graph theory
• Chords of longest cycles passing through a specified small set
• Chords of longest cycles in graphs with large circumferences