The b-chromatic number of a graph

The b-chromatic number of a graph

0.00 Avg rating0 Votes
Article ID: iaor20001708
Country: Netherlands
Volume: 91
Issue: 1/3
Start Page Number: 127
End Page Number: 141
Publication Date: Jan 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: computational analysis
Abstract:

The achromatic number ψ(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 ψ(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, ψ(G), of G. We prove that determining ψ(G) is NP-hard for general graphs, but polynomial-time solvable for trees.

Reviews

Required fields are marked *. Your email address will not be published.