✦ LIBER ✦

Critical perfect graphs and perfect 3-chromatic graphs

✍ Scribed by Alan Tucker

Publisher: Elsevier Science
Year: 1977
Tongue: English
Weight: 394 KB
Volume: 23
Category: Article
ISSN: 0095-8956
DOI: 10.1016/0095-8956(77)90064-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

A new method to extend kernel-perfect gr

A new method to extend kernel-perfect graphs to kernel-perfect critical graphs

✍ Hortensia Galeana-Sánchez 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 200 KB

## Comnnmicated by G. Berge In [3] Galeana-Stinchez and Neumann-Lara have deveioped a genera! method to extend kernel-perfect graphs to kernel-perfect critical graphs. In this note we construct a class of kernel-perfect critical graphs which can be used to extend any kernel-perfect graph. For gen

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 &

On a class of kernel-perfect and kernel-

On a class of kernel-perfect and kernel-perfect-critical graphs

✍ Kiran B. Chilakamarri; Peter Hamburger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 275 KB

Chilakamarri, K.B. and P. Hamburger, On a class of kernel-perfect and kernel-perfect-critical graphs, Discrete Mathematics 118 (1993) 253-257. In this note we present a construction of a class of graphs in which each of the graphs is either kernel-perfect or kernel-perfect-critical. These graphs or

Circular perfect graphs

✍ Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 209 KB

For 1 d k, let K k=d be the graph with vertices 0; 1; . . . ; k À 1, in which i $ j if d ji À jj k À d. The circular chromatic number c ðGÞ of a graph G is the minimum of those k=d for which G admits a homomorphism to K k=d . The circular clique number ! c ðGÞ of G is the maximum of those k=d for wh