Every longest circuit of a 3‐connected,K3,3‐minor free graph has a chord

DOI10.1002/JGT.20312MaRDI QIDQ3630835zbMATH OpenOpenAlexFDO

Authors Etienne Birmelé

Publication date 4 June 2009

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

3-connectedlongest circuitminor free graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

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.

Recommendations

• Chords of longest circuits in 3-connected graphs
• scientific article; zbMATH DE number 3902690
• Every 3-connected \(\{K_{1,3},N_{3,3,3}\}\)-free graph is Hamiltonian
• scientific article; zbMATH DE number 1150168
• Longest paths and cycles in K1,3-free graphs
• Every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected
• Minimally 3-connected graphs with exactly k non-essential edges
• scientific article; zbMATH DE number 238370
• scientific article; zbMATH DE number 980260
• The circumference of a graph with no \(K_{3,t}\)-minor

Cites work

• Chords of longest circuits in 3-connected graphs
• Chords of longest circuits in locally planar graphs
• Chords of longest circuits of graphs embedded in torus and Klein bottle
• Chords of longest cycles in cubic graphs
• Graph theory with applications
• Longest cycles and their chords

Cited in

(14)

• Chords of longest circuits in 3-connected graphs
• A cycle of maximum order in a graph of high minimum degree has a chord
• The circumference of a graph with no \(K_{3,t}\)-minor. II
• Removable edges and chords of longest cycles in 3-connected graphs
• Results and problems on chorded cycles: a survey
• A generalization of chordal graphs
• Longest cycles and their chords
• Chords of longest circuits of graphs embedded in torus and Klein bottle
• Chords in longest cycles
• Chords of longest cycles passing through a specified small set
• Longest cycles and longest chordless cycles in 2-connected graphs
• Chords of longest cycles in 3-connected graphs with some special circumferences
• Chords of longest cycles in graphs with large circumferences
• A refinement of Kuratowski's theorem

This page was built for publication: Every longest circuit of a 3‐connected,K_3,3‐minor free graph has a chord

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