Every $3$-connected, essentially $11$-connected line graph is hamiltonian
Résumé
Thomassen conjectured that every $4$-connected line graph is hamiltonian. A vertex cut $X$ of $G$ is essential if $G-X$ has at least two nontrivial components. We prove that every $3$-connected, essentially $11$-connected line graph is hamiltonian. Using Ryjáček's line graph closure, it follows that every $3$-connected, essentially $11$-connected claw-free graph is hamiltonian.
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...