✦ LIBER ✦

On critically perfect graphs

✍ Scribed by Wagler, Annegret

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 337 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199912)32:4<394::aid-jgt7>3.0.co;2-z

No coin nor oath required. For personal study only.

✦ Synopsis

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, and study operations preserving critical perfectness.

📜 SIMILAR VOLUMES

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

Cycle-perfect graphs are perfect

✍ Le, Van Bang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB 👁 1 views

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 &

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

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

Long cycles in critical graphs

✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 2 views

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