𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Equivalence of Fleischner's and Thomassen's Conjectures

✍ Scribed by Martin Kochol

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
96 KB
Volume
78
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We show that conjectures of Thomassen (every 4-connected line graph is hamiltonian) and Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle) are equivalent.

📜 SIMILAR VOLUMES

On the Thomassen's conjecture
On the Thomassen's conjecture
✍ Jianping Li 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 152 KB

## Abstract C. Thomassen proposed a conjecture: Let __G__ be a __k__‐connected graph with the stability number α ≥ __k__, then __G__ has a cycle __C__ containing __k__ independent vertices and all their neighbors. In this paper, we will obtain the following result: Let __G__ be a __k__‐connected gr

Subcontraction-equivalence and Hadwiger'
Subcontraction-equivalence and Hadwiger's conjecture
✍ D. R. Woodall 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 350 KB

The concept of subcontraction-equivalence is defined, and 14 graphtheoretic properties are exhibited that are all subcontraction-equivalent if Hadwiger's conjecture is true. Some subsets of these properties are proved to be subcontraction-equivalent anyway. Hadwiger's conjecture is expressed as the

On a conjecture of Thomassen and Toft
On a conjecture of Thomassen and Toft
✍ Kriesell, Matthias 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 2 views

This article is motivated by a conjecture of Thomassen and Toft on the number s 2 (G) of separating vertex sets of cardinality 2 and the number v 2 (G) of vertices of degree 2 in a graph G belonging to the class G of all 2-connected graphs without nonseparating induced cycles. Let G denote the numbe

Thomassen's conjecture implies polynomia
Thomassen's conjecture implies polynomiality of 1-Hamilton-connectedness in line graphs
✍ Roman Kužel; Zdeněk Ryjáček; Petr Vrána 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 158 KB

## Abstract A graph __G__ is 1‐Hamilton‐connected if __G__−__x__ is Hamilton‐connected for every __x__∈__V__(__G__), and __G__ is 2‐edge‐Hamilton‐connected if the graph __G__+ __X__ has a hamiltonian cycle containing all edges of __X__ for any __X__⊂__E__^+^(__G__) = {__xy__| __x, y__∈__V__(__G__)}

The equivalence of two conjectures of Be
The equivalence of two conjectures of Berge and Fulkerson
✍ G. Mazzuoccolo 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 65 KB

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1-factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge-set of G can be covered with at most five 1-factors. We prove that the two conjectures are equivalent.