Computing at Glasgow University
Paper ID: 5358

The b-chromatic number of a graph
Irving,R.W. Manlove,D.F.

Publication Type: Journal
Appeared in: Discrete Applied Mathematics, volume 91
Page Numbers : 127-141
Publisher: Elsevier Science
Year: 1999
ISBN/ISSN: 0166-218X

URL: This publication is available at this URL.


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.

Keywords: Complexity; graph; colouring; achromatic; b-chromatic

PDF Bibtex entry Endnote XML