Partial Proofs of Thomassen's Conjecture
Séminaire lotharingien de combinatoire, Tome 30 (1993)
Citer cet article
Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website
THOMASSEN's Conjecture (1986) claims that every line-graph with vertex-connectivity number κ ≥ 4 is hamiltonian. This conjecture is equivalent to several other conjectures. The partial proofs which will be summed up here do not start directly from a line-graph, but from a graph «I>G such that its line-graph L(G) has the properties as above. It will be shown that both G and L(G) must fulfill a great number of restrictions if L(G) is to be a counterexample to THOMASSEN's Conjecture. These restrictions are both structural properties and inequalities related to several graph invariants. It is proved e.g. that a counterexample must have at least 23 vertices, it has a 2-cover, and it is not locally connected.