Hamiltonian cycles in line graphs

Status partial high confidence

Thomassen's conjecture that every 4-connected line graph is Hamiltonian remains open. Partial progress includes lowering the sufficient connectivity threshold: any 5-connected line graph with minimum degree at least 6 is Hamiltonian (Kaiser–Vrána), and several equivalent reformulations have been established. The conjecture is also equivalent to the Matthews–Sumner conjecture (every 4-connected claw-free graph is Hamiltonian), and both remain unresolved.

Cited literature (3)

• partial Hamilton cycles in 5-connected line graphs (2012)
  Tomáš Kaiser, Petr Vrána · European Journal of Combinatorics · arXiv:1009.3754

  Any 5-connected line graph with minimum degree at least 6 is Hamiltonian, lowering the sufficient connectivity threshold from 7-connected toward the conjectured 4-connected.

• reduction Equivalent formulation of Thomassen's conjecture using Tutte paths in claw-free graphs (2019)
  Adam Kabela, Zdeněk Ryjáček, Petr Vrána · arXiv preprint · arXiv:1907.08029

  Thomassen's conjecture is equivalent to the statement that in every connected claw-free graph, every two vertices are connected by a Tutte path, extending the known equivalence with Jackson's Tutte cycle conjecture.

• partial Hamiltonian Properties of 3-Connected Claw-Free Graphs and Line Graphs of 3-Hypergraphs (2026)
  Kenta Ozeki, Leilei Zhang · arXiv preprint · arXiv:2603.03361

  Every 3-connected claw-free graph with domination number at most 5 is Hamiltonian (with finitely many exceptions), and related Hamiltonian results for line graphs of 3-hypergraphs are established.

Reviewer notes. ScienceDirect pages for Kaiser–Vrána (European J. Combinatorics) and the 2020 'Thomassen's conjecture for line graphs of 3-hypergraphs' paper returned 403 errors; venue for Kaiser–Vrána is inferred from the ScienceDirect URL pattern (ISSN 0195-6698 = European J. Combinatorics) with estimated publication year 2012. The 2019 Kabela–Ryjáček–Vrána preprint was revised in 2025, suggesting it may have been published in a journal by then. The conjecture is also equivalent to Fleischner's dominating cycle conjecture for snarks.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 06) (web search enabled).