✦ LIBER ✦

Claw-free circular-perfect graphs

✍ Scribed by Arnaud Pêcher; Xuding Zhu

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 112 KB
Volume: 65
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20474

No coin nor oath required. For personal study only.

✦ Synopsis

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 if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010

📜 SIMILAR VOLUMES

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

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

Circular perfect graphs

✍ Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

For 1 d k, let K k=d be the graph with vertices 0; 1; . . . ; k À 1, in which i $ j if d ji À jj k À d. The circular chromatic number c ðGÞ of a graph G is the minimum of those k=d for which G admits a homomorphism to K k=d . The circular clique number ! c ðGÞ of G is the maximum of those k=d for wh

Almost claw-free graphs

✍ Zdeněk Ryjáček 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

## 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

Well-Covered Claw-Free Graphs

✍ David Tankus; Michael Tarsi 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 336 KB

Hamilton cycles in claw-free graphs

✍ Cun-Quan Zhang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 2 views