𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A decomposition for strongly perfect graphs

✍ Scribed by Stephan Olariu

Publisher
John Wiley and Sons
Year
1989
Tongue
English
Weight
554 KB
Volume
13
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is strongly perfect if every induced subgraph H of G contains a stable set that meets all the maximal cliques of H . We present a graph decomposition that preserves strong perfection: more precisely, a stitch decomposition of a graph G = (V, €1 is a partition of V into nonempty disjoint subsets V,, V, such that in every P4 with vertices in both K's, each of the three edges has an endpoint in V, and the other in V,.

We give a good characterization of graphs that admit a stitch decomposition and establish several results concerning the stitch decomposition of strongly perfect graphs.

📜 SIMILAR VOLUMES

s-strongly perfect cartesian product of
s-strongly perfect cartesian product of graphs
✍ Elefterie Olaru; Eugen Mǎndrescu 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

## Abstract The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (__Discrete Mathematics__, Vol. 20, 1977, pp. 177‐‐186), G. Ravindra and K. R.

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

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