✦ LIBER ✦

A Characterization of b-Perfect Graphs

✍ Scribed by Chính T. Hoàng; Frédéric Maffray; Meriem Mechebbek

Publisher: John Wiley and Sons
Year: 2011
Tongue: English
Weight: 316 KB
Volume: 71
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20635

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012

📜 SIMILAR VOLUMES

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

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

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 semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl

A Description of Claw-Free Perfect Graph

A Description of Claw-Free Perfect Graphs

✍ Frédéric Maffray; Bruce A. Reed 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 249 KB

It is known that all claw-free perfect graphs can be decomposed via clique-cutsets into two types of indecomposable graphs respectively called elementary and peculiar (1988, V. Chva tal and N. Sbihi, J. Combin. Theory Ser. B 44, 154 176). We show here that every elementary graph is made up in a well

A note on Ki-perfect graphs

✍ Jason I. Brown; Derek G. Corneil; A. Ridha Mahjoub 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## 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__