✦ LIBER ✦

On the Thomassen's conjecture

✍ Scribed by Jianping Li

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 152 KB
Volume: 37
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1011

No coin nor oath required. For personal study only.

✦ Synopsis

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 graph with stability number α = k + 3 and C any longest cycle of G, then C contains k independent vertices and all their neighbors. This solves Thomassen's conjecture for the case α = k + 3. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 168–180, 2001

📜 SIMILAR VOLUMES

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

Equivalence of Fleischner's and Thomasse

Equivalence of Fleischner's and Thomassen's Conjectures

✍ Martin Kochol 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 96 KB

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.

On a conjecture of Thomassen concerning

On a conjecture of Thomassen concerning subgraphs of large girth

✍ Domingos Dellamonica Jr; Václav Koubek; Daniel M. Martin; Vojtěch Rödl 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB

In 1983 C. Thomassen conjectured that for every k, g ∈ N there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kühn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based

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__)}

On the Erd�s-S�s conjecture

✍ Wo?niak, Mariusz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB

Erdos and Sos conjectured in 1963 that if G is a graph of order n and size e(G) with e(G) > $ n(k -I), then G contains every tree T of size k. W e present some partial results; in particular the proof of the conjecture in the case k = n -3 0 1996 John

On Kummer's Conjecture

✍ M.Ram Murty; Yiannis N Petridis 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 120 KB

Kummer conjectured the asymptotic behavior of the first factor of the class number of a cyclotomic field. If we only ask for upper and lower bounds of the order of growth predicted by Kummer, then this modified Kummer conjecture is true for almost all primes.