𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On factors of 4-connected claw-free graphs

✍ Scribed by H. J. Broersma; M. Kriesell; Z. Ryjác̆ek

Publisher
John Wiley and Sons
Year
2001
Tongue
English
Weight
105 KB
Volume
37
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001

📜 SIMILAR VOLUMES

9-Connected Claw-Free Graphs Are Hamilto
9-Connected Claw-Free Graphs Are Hamilton-Connected
✍ Stephan Brandt 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 130 KB

A graph is Hamilton-connected if any pair of vertices is joined by a hamiltonian path. In this note it is shown that 9-connected graphs which contain no induced claw K 1, 3 are Hamilton-connected, by reformulating and localizing a closure concept due to Ryja c ek, which turns claw-free graphs into l

Non-traceability of large connected claw
Non-traceability of large connected claw-free graphs
✍ Frydrych, Wac?w; Skupie?, Zdzis?aw 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB 👁 3 views

Let G be a connected claw-free graph on n vertices. Let σ 3 (G) be the minimum degree sum among triples of independent vertices in G. It is proved that if σ 3 (G) ≥ n-3 then G is traceable or else G is one of graphs G n each of which comprises three disjoint nontrivial complete graphs joined togethe

Hamiltonian N2-locally connected claw-fr
Hamiltonian N2-locally connected claw-free graphs
✍ Hong-Jian Lai; Yehong Shao; Mingquan Zhan 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

A graph G is N 2 -locally connected if for every vertex v in G, the edges not incident with v but having at least one end adjacent to v in G induce a connected graph. In 1990, Ryja ´c ˇek conjectured that every 3-connected N 2 -locally connected claw-free graph is Hamiltonian. This conjecture is pro

Critical graphs for subpancyclicity of 3
Critical graphs for subpancyclicity of 3-connected claw-free graphs
✍ Ronald J. Gould; Tomasz Łuczak; Florian Pfender 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract Let ${\cal{F}}\_{k}$ be the family of graphs __G__ such that all sufficiently large __k__ ‐connected claw‐free graphs which contain no induced copies of __G__ are subpancyclic. We show that for every __k__≥3 the family ${\cal{F}}\_{1}k$ is infinite and make the first step toward the c