On minimally b-imperfect graphs |
| |
Authors: | Chí nh T. Ho ng, Cl udia Linhares Sales,Fr d ric Maffray |
| |
Affiliation: | aDepartment of Physics and Computer Science, Wilfrid Laurier University, 75 University Avenue West, Waterloo, Ontario, Canada N2L 3C5;bDepartamento de Computação, Universidade Federal do Ceará, Campus do Pici, Fortaleza, CE, Brazil;cC.N.R.S, Laboratoire G-SCOP, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France |
| |
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 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 H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list 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. |
| |
Keywords: | Coloration b-coloring a-chromatic number b-chromatic number |
本文献已被 ScienceDirect 等数据库收录! |
|