𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Even Pairs in Claw-Free Perfect Graphs

✍ Scribed by Cláudia Linhares Sales; Frédéric Maffray

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
424 KB
Volume
74
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 turned into a clique through a sequence of even-pair contractions. In this paper we determine the K 1, 3 -free graphs that are strict quasi-parity and those that are perfectly contractile. We show that for both classes the minimal forbidden configurations are odd holes, antiholes and some line-graphs of bipartite graphs, as conjectured by several authors. Our proofs are constructive and yield polynomial-time algorithms for the recognition of both classes.

📜 SIMILAR VOLUMES

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

A Description of Claw-Free Perfect Graph
A Description of Claw-Free Perfect Graphs
✍ Frédéric Maffray; Bruce A. Reed 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 249 KB

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

Perfect pairs of trees in graphs
Perfect pairs of trees in graphs
✍ Ladislav Novak; Alan Gibbons 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 392 KB
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 Γ~__

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