✦ LIBER ✦

On wing-perfect graphs

✍ Scribed by Hougardy, Stefan

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 342 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199905)31:1<51::aid-jgt5>3.0.co;2-y

No coin nor oath required. For personal study only.

✦ Synopsis

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 belong to the same P 4 . We will characterize all graphs whose wing-graph is a cycle. This solves a conjecture posed by Hoàng [9].

📜 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

On critically perfect graphs

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

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

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

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

On the perfect orderability of unions of

On the perfect orderability of unions of two graphs

✍ Ho�ng, Ch�nh T.; Tu, Xiaodan 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 264 KB 👁 2 views

A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P 4 , 2K 2 , and C 4 as induced subgraph. A theorem of Chvátal