The b-chromatic number of a graph
- Publisher: Elsevier
Discrete Applied Mathematics
(issn: 0166-218X, vol:
Applied Mathematics | QA75 | Discrete Mathematics and Combinatorics
The achromatic number psi(G) of a graph G = (V,E) is the maximum k such that V has a partition V1, V2,...,Vk into independent sets, the union of no pair of which is independent. Here we show that psi(G) can be viewed as the maximum over all minimal elements of a partial order defined on the set of all colourings of G. We introduce a natural refinement of this partial order, giving rise to a new parameter, which we call the b-chromatic number, varphi(G), of G. We prove that determining varphi(G) is NP-hard for general graphs, but polynomial-time solvable for trees.