A Characterization of b‐Perfect Graphs
Authors:
- 1 December 2011
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 71 (1) , 95-122
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, 2012Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- On minimally b-imperfect graphsDiscrete Applied Mathematics, 2009
- On b-perfect Chordal GraphsGraphs and Combinatorics, 2009
- The strong perfect graph theoremAnnals of Mathematics, 2006
- On the b-dominating coloring of graphsDiscrete Applied Mathematics, 2005
- On the b-Chromatic Number of Graphs2002
- The b-chromatic number of a graphDiscrete Applied Mathematics, 1999
- On the complexity of recognizing perfectly orderable graphsDiscrete Mathematics, 1990
- Weakly triangulated graphsJournal of Combinatorial Theory, Series B, 1985
- On a property of the class of n-colorable graphsJournal of Combinatorial Theory, Series B, 1974