✦ LIBER ✦

A Description of Claw-Free Perfect Graphs

✍ Scribed by Frédéric Maffray; Bruce A. Reed

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 249 KB
Volume: 75
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1872

No coin nor oath required. For personal study only.

✦ Synopsis

It is known that all claw-free perfect graphs can be decomposed via clique-cutsets into two types of indecomposable graphs respectively called elementary and peculiar (1988, V. Chva tal and N. Sbihi, J. Combin. Theory Ser. B 44, 154 176). We show here that every elementary graph is made up in a well-defined way of a linegraph of bipartite graph and some local augments consisting of complements of bipartite graphs. This yields a complete description of the structure of claw-free Berge graphs and a new proof of their perfectness.

📜 SIMILAR VOLUMES

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

Even Pairs in Claw-Free Perfect Graphs

✍ Cláudia Linhares Sales; Frédéric Maffray 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 424 KB

An even pair in a graph is a pair of non-adjacent vertices such that every chordless path between them has even length. A graph is called strict quasi-parity when every induced subgraph that is not a clique has an even pair, and it is called perfectly contractile when every induced subgraph can be t

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

On a Closure Concept in Claw-Free Graphs

✍ Zdeněk Ryjáček 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 269 KB

If G is a claw-free graph, then there is a graph cl(G) such that (i) G is a spanning subgraph of cl(G), (ii) cl(G) is a line graph of a triangle-free graph, and (iii) the length of a longest cycle in G and in cl(G) is the same. A sufficient condition for hamiltonicity in claw-free graphs, the equiv

Upper total domination in claw-free grap

Upper total domination in claw-free graphs

✍ Odile Favaron; Michael A. Henning 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB

## Abstract A set __S__ of vertices in a graph __G__ is a total dominating set of __G__ if every vertex of __G__ is adjacent to some vertex in __S__ (other than itself). The maximum cardinality of a minimal total dominating set of __G__ is the upper total domination number of __G__, denoted by Γ~__

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