Importance: High ✭✭✭
Author(s): Thomassen, Carsten
Recomm. for undergrads: no
Posted by: Robert Samal
on: July 24th, 2007
Conjecture   Every 4-connected line graph is hamiltonian.
  • It is known that if $ G $ is 4-edge-connected, then its line graph $ L(G) $ is hamiltonian.
  • Thomassen's is a special case of a conjecture due to Matthews and Sumner: every 4-connected claw-free graph is hamiltonian.
  • However, by a result of Ryjacek [R] conjectures of Thomassen and of Matthews and Sumner are equivalent.
  • Moreover [R], one may restrict to 4-connected line graphs of triangle-free graphs.

Bibliography

[R] Zdenek Ryjacek: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B 70 (1997), no. 2, 217--224, MathSciNet

*[T] Carsten Thomassen, Reflections on graph theory, J. Graph Theory 10 (1986) 309-324, MathSciNet


* indicates original appearance(s) of problem.

Reply

Comments are limited to a maximum of 1000 characters.