✦ LIBER ✦

A generalization of perfect graphs?i-perfect graphs

✍ Scribed by Cai, Leizhen; Corneil, Derek

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 1003 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199609)23:1<87::aid-jgt10>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

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 induced by each V,, 1 5 j 5 k, is at most i. The i-clique numbel; denoted by w,(G), is the i-chromatic number of a largest clique in G, which

We generalize the notion of perfect graphs as follows:

(1 1 A graph G is z-pegect iff x 2 ( H ) = w Z ( H ) for every induced subgraph H of G.

(2) A graph G isperfectly i-trunsversable iff either w(G) 5 i or every induced subgraph H of G with w ( H ) > i contains an i-transversal of H.

We study the relationships among i-perfect graphs and perfectly i-transversable graphs. In particular, we show that 1 -perfect graphs and perfectly 1 -transversable graphs both coincide with perfect graphs, and that perfectly i-transversable graphs form a strict subset of i-perfect graphs for every i 2 2. We also show that all planar graphs are iperfect for every i 2 2 and perfectly i-transversable for every i 2 3; the latter implies

📜 SIMILAR VOLUMES

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 &

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

β-Perfect Graphs

✍ S.E. Markossian; G.S. Gasparian; B.A. Reed 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 291 KB

The class of ;-perfect graphs is introduced. We draw a number of parallels between these graphs and perfect graphs. We also introduce some special classes of ;-perfect graphs. Finally, we show that the greedy algorithm can be used to colour a graph G with no even chordless cycles using at most 2(/(G

A characterization of domination perfect

A characterization of domination perfect graphs

✍ I. E. Zverovich; V. E. Zverovich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Let u(G) and i(G) be the domination number and independent domination number of a graph G. respectively. Sumner and Moore [8] define a graph G to be domination perfect if y( H) = i( H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization o

Coloring precolored perfect graphs

✍ Kratochv�l, Jan; Seb?, Andr�s 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 2 views

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vert

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