<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>5358</REFNUM><AUTHORS><AUTHOR>Irving,R.W.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>1999</YEAR><TITLE>The b-chromatic number of a graph</TITLE><PLACE_PUBLISHED>Discrete Applied Mathematics, volume 91</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>127-141</PAGES><ISBN>0166-218X</ISBN><LABEL>Irving:1999:5358</LABEL><KEYWORDS><KEYWORD>Complexity; graph; colouring; achromatic; b-chromatic</KEYWORD></KEYWORDS<ABSTRACT>The achromatic number \psi(G) of a graph G = (V,E) is the maximum k such that V has a partition V<sub>1</sub>, V<sub>2</sub>,...,V<sub>k</sub> 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.</ABSTRACT><URL>http://dx.doi.org/doi:10.1016/S0166-218X(98)00146-2</URL></RECORD></RECORDS></XML>