✦ LIBER ✦

Wings and perfect graphs

✍ Scribed by Stephen Olariu

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 999 KB
Volume: 80
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90248-g

No coin nor oath required. For personal study only.

✦ Synopsis

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in

and some vertex in C is adjacent to all the remaining vertices in C. V. Chvatal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.

📜 SIMILAR VOLUMES

On wing-perfect graphs

✍ Hougardy, Stefan 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 2 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

Wing-triangulated graphs are perfect

✍ Hougardy, Stefan; Le, Van Bang; Wagler, Annegret 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 100 KB 👁 2 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

Critical perfect graphs and perfect 3-ch

Critical perfect graphs and perfect 3-chromatic graphs

✍ Alan Tucker 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 394 KB

Reconstructibility and perfect graphs

✍ Michael Von Rimscha 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 738 KB

It is shown that the following classes of graphs are recognizable (i.e. looking at the point-deleted subgraphs of a graph G one can decide whether G belongs to that class or not): (1) perfect graphs, (2) triangulated graphs, (3) interval graphs, (4) comparability graphs, (5) split graphs. Furthermor

A generalization of perfect graphs?i-per

A generalization of perfect graphs?i-perfect graphs

✍ Cai, Leizhen; Corneil, Derek 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc

Cycle-perfect graphs are perfect

✍ Le, Van Bang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB 👁 2 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 &