A Characterization of b‐Perfect Graphs |
| |
| Authors: | Chính T Hoàng Frédéric Maffray Meriem Mechebbek |
| |
| Institution: | 1. Department of Physics and Computer Science, Wilfrid Laurier University, 75 University Avenue West, , Ontario, Canada, N2L 3C5;2. C.N.R.S, Laboratoire G‐Scop, UMR 5272, Grenoble‐Inp, UJF‐Grenoble 1, , Grenoble, France;3. Usthb, Laboratoire Laid3, Bp32 El Alia, , Alger, Algeria |
| |
| 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 |
| |
| Keywords: | Coloration b‐coloring a‐chromatic number b‐chromatic number |
|
|
