𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Families of graphs complete for the strong perfect graph Conjecture

✍ Scribed by D. G. Corneil

Publisher
John Wiley and Sons
Year
1986
Tongue
English
Weight
381 KB
Volume
10
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 iff it is true on these restricted families. These appear to be the first results of this type.

πŸ“œ SIMILAR VOLUMES

On the strong perfect graph conjecture
On the strong perfect graph conjecture
✍ Stephan Olariu πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 384 KB

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 cho

A Family of Perfect Factorisations of Co
A Family of Perfect Factorisations of Complete Bipartite Graphs
✍ Darryn Bryant; Barbara M. Maenhaut; Ian M. Wanless πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 493 KB

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n=p 2 for an odd prime p. We construct a family of ( p -1)/2 non-isomorphic perfect 1-factorisations of K n, n . Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin s

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 perfect Ξ“-decompositions of the compl
On perfect Ξ“-decompositions of the complete graph
✍ Marco Buratti; Anita Pasotti πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 155 KB

## Abstract Generalizing the well‐known concept of an __i__‐perfect cycle system, Pasotti [Pasotti, in press, Australas J Combin] defined a Γ‐decomposition (Γ‐factorization) of a complete graph __K__~__v__~ to be __i‐perfect__ if for every edge [__x__, __y__] of __K__~__v__~ there is exactly one bl

On the conjecture for certain Laplacian
On the conjecture for certain Laplacian integral spectrum of graphs
✍ Kinkar Ch. Das; Sang-Gu Lee; Gi-Sang Cheon πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 184 KB πŸ‘ 1 views

## Abstract Let __G__ be a simple graph of order __n__ with Laplacian spectrum {Ξ»~__n__~, Ξ»~__n__βˆ’1~, …, Ξ»~1~} where 0=Ξ»~__n__~≀λ~__n__βˆ’1~≀⋅≀λ~1~. If there exists a graph whose Laplacian spectrum is __S__={0, 1, …, __n__βˆ’1}, then we say that __S__ is Laplacian realizable. In 6, Fallat et al. posed