✦ LIBER ✦

Cycle-perfect graphs are perfect

✍ Scribed by Le, Van Bang

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 177 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199612)23:4<351::aid-jgt3>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. 0 1996 John Wiley &

📜 SIMILAR VOLUMES

Wing-triangulated graphs are perfect

✍ Hougardy, Stefan; Le, Van Bang; Wagler, Annegret 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 1 views

The wing-graph W (G) of a graph G has all edges of G as its vertices; two edges of G are adjacent in W (G) if they are the nonincident edges (called wings) of an induced path on four vertices in G. Hoàng conjectured that if W (G) has no induced cycle of odd length at least five, then G is perfect. A

Coloring precolored perfect graphs

✍ Kratochv�l, Jan; Seb?, Andr�s 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vert

On wing-perfect graphs

✍ Hougardy, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

An edge in a graph G is called a wing if it is one of the two nonincident edges of an induced P 4 (a path on four vertices) in G. For a graph G, its winggraph W (G) is defined as the graph whose vertices are the wings of G, and two vertices in W (G) are connected if the corresponding wings in G belo

On critically perfect graphs

✍ Wagler, Annegret 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 337 KB 👁 1 views

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, a

Irredundance perfect andP6-free graphs

✍ Puech, Jo�l 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 307 KB

The domination number γ(G) and the irredundance number ir(G) of a graph G have been considered by many authors. It is well known that ir(G) ≤ γ(G) holds for all graphs G, which leads us to consider the concept of irredundance perfect graphs: graphs that have all their induced subgraphs satisfying th

How Perfect You Are

✍ Isabel Fox 📂 Fiction 📅 2019 🌐 English ⚖ 154 KB 👁 3 views

A mystery Novel.