𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Almost claw-free graphs

✍ Scribed by Zdeněk Ryjáček

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
374 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We say that G is almost claw‐free if the vertices that are centers of induced claws (K~1,3~) in G are independent and their neighborhoods are 2‐dominated. Clearly, every claw‐free graph is almost claw‐free. It is shown that (i) every even connected almost claw‐free graph has a perfect matching and (ii) every nontrivial locally connected K~1,4~‐free almost claw‐free graph is fully cycle extendable.

📜 SIMILAR VOLUMES

Toughness and hamiltonicity in almost cl
Toughness and hamiltonicity in almost claw-free graphs
✍ Broersma, H.J.; Ryj�?ek, Z.; Schiermeyer, I. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 3 views

Some known results on claw-free (Kl,3-free) graphs are generalized to the larger class of almost claw-free graphs which were introduced by RyjaEek. In particular, w e show that a 2-connected almost claw-free graph is I-tough, and that a 2-connected almost claw-free graph on n vertices is hamiltonian

Claw-free circular-perfect graphs
Claw-free circular-perfect graphs
✍ Arnaud Pêcher; Xuding Zhu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 112 KB

## Abstract The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that

Well-Covered Claw-Free Graphs
Well-Covered Claw-Free Graphs
✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB
Claw-free graphs are edge reconstructibl
Claw-free graphs are edge reconstructible
✍ M. N. Ellingham; L. Pyber; Xingxing Yu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 318 KB 👁 1 views

The Edge Reconstruction Conjecture states that all graphs with at least four edges are determined by their edge-deleted subgraphs. We prove that this is true for claw-free graphs, those graphs with no induced subgraph isomorphic to K,,3. This includes line graphs as a special case.

Hamilton connectivity of line graphs and
Hamilton connectivity of line graphs and claw-free graphs
✍ Zhiquan Hu; Feng Tian; Bing Wei 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 117 KB

## Abstract Let __G__ be a graph and let __V__~0~ = {ν∈ __V__(__G__): __d__~__G__~(ν) = 6}. We show in this paper that: (i) if __G__ is a 6‐connected line graph and if |__V__~0~| ≤ 29 or __G__[__V__~0~] contains at most 5 vertex disjoint __K__~4~'s, then __G__ is Hamilton‐connected; (ii) every 8‐co