Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420473 | Discrete Applied Mathematics | 2009 | 12 Pages |
Abstract
A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph GG is the largest integer kk such that GG admits a b-coloring with kk colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph HH of GG. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list FF of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chính T. Hoàng, Cláudia Linhares Sales, Frédéric Maffray,