The b-chromatic number of a graph (Q1283791)

The achromatic number of a graph \(G= (V,E)\) is the maximum \(k\) such that \(V\) can be partitioned into \(k\) independent sets with no union of a pair of these sets again independent. The authors show that this can be expressed using a partial order on the set of partitions of \(V\). A partition is said to be smaller than another partition if it can be obtained from the latter by replacing two sets by their union, or by a transitive closure of this relation. Then the achromatic number is the maximum size of a minimal element under this partial order of the partitions of \(V\) into independent sets. If we take another partial order, using instead of taking the union, the distribution of elements of one set over the other sets, then the parameter obtained is the newly introduced b-chromatic number of the graph. Alternatively, the b-chromatic number of a graph \(G= (V,E)\) an be defined as the maximum \(k\), such that \(V\) can be partitioned into \(k\) independent sets such that each independent set contains at least one vertex that is adjacent to each other independent set. The b-chromatic number problem is shown to be NP-complete. Also, the authors show that the problem can be solved exactly for trees, giving a precise characterization of the b-chromatic number. This characterization is in terms of the degrees of the vertices and adjacencies of vertices with vertices of certain degrees, and can easily be checked in linear time.