✦ LIBER ✦

On the strong perfect graph conjecture

✍ Scribed by Stephan Olariu

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 384 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120206

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd chordless cycle of length at least 5. Its resolution has eluded researchers for more than 20 years. We prove that the conjecture is true for a class of graphs that we describe by forbidden configurations.

📜 SIMILAR VOLUMES

Families of graphs complete for the stro

Families of graphs complete for the strong perfect graph Conjecture

✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true

Proof of a conjecture on irredundance pe

Proof of a conjecture on irredundance perfect graphs

✍ Lutz Volkmann; Vadim E. Zverovich 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

## Abstract Let __ir__(__G__) and γ(__G__) be the irredundance number and the domination number of a graph __G__, respectively. A graph __G__ is called __irredundance perfect__ if __ir__(__H__)=γ(__H__), for every induced subgraph __H__ of __G__. In this article we present a result which immediatel

On the critical graph conjecture

✍ Hian Poh Yap 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 222 KB

## Abstract Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a __p__(≥4)‐critical graph __K__ of odd order such that __K__ has a vertex __u__ of valency 2 and another vertex __v__ ≠ __u__ of valency ≤(__p__ + 2)/2, then ther

Solution of fink & straight conjecture o

Solution of fink & straight conjecture on path-perfect complete bipartite graphs

✍ Weiting Cao; Peter Hamburger 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

## Abstract We consider various edge disjoint partitions of complete bipartite graphs. One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph __G__ is __path‐perfect__ if there is a positive integer __n__ such that the edge set __E__(__G__) of the graph

On the strong circular 5-flow conjecture

✍ Edita Máčajová; André Raspaud 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

## Abstract The Strong Circular 5‐flow Conjecture of Mohar claims that each snark—with the sole exception of the Petersen graph—has circular flow number smaller than 5. We disprove this conjecture by constructing an infinite family of cyclically 4‐edge connected snarks whose circular flow number eq

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