✦ LIBER ✦

A note on Ki-perfect graphs

✍ Scribed by Jason I. Brown; Derek G. Corneil; A. Ridha Mahjoub

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 348 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140306

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Ki‐perfect graphs are a special instance of F ‐ G perfect graphs, where F and G are fixed graphs with F a partial subgraph of G. Given S, a collection of G‐subgraphs of graph K, an F ‐ G cover of S is a set of T of F‐subgraphs of K such that each subgraph in S contains as a subgraph a member of T. An F ‐ G packing of S is a subcollection S′⊆ S such that no two subgraphs in S′ have an F‐subgraph in common. K is F ‐ G perfect if for all such S, the minimum cardinality of an F ‐ G cover of S equals the maximum cardinality of an F ‐ G packing of S. Thus K~i~‐perfect graphs are precisely K~i‐1~ ‐ K~i~ perfect graphs. We develop a hypergraph characterization of F ‐ G perfect graphs that leads to an alternate proof of previous results on K~i~‐perfect graphs as well as to a characterization of F ‐ G perfect graphs for other instances of F and G.

📜 SIMILAR VOLUMES

A note on the characterization of domina

A note on the characterization of domination perfect graphs

✍ Jason Fulman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

## Abstract A graph __G__ is domination perfect if for each induced subgraph __H__ of __G__, γ(__H__) = __i__(__H__), where γ and __i__ are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of

A Note on Perfect Isometries

✍ Geoffrey R. Robinson 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 94 KB

## Ž . B which take constant non-zero ¨alues on p-singular elements. 1 Furthermore, it is always possible to modify the perfect isometry so that it sends the trivial character of H to the trivial character of G.

A note on conservative graphs

✍ Arthur T. White 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB

## Abstract An application of conservative graphs to topological graph theory is indicated.

A note on coset graphs

✍ Ulrike Baumann 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

## Abstract Coset graphs are a generalization of Cayley graphs. They arise in the construction of graphs and digraphs with transitive automorphism groups. Moreover, the consideration of coset graphs makes it possible to give an algebraic description of regular connected graphs of even degree. In th

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

On critically perfect graphs

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

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