The b-chromatic number of a graph
type: Item
instance of: scholarly article
title: The b-chromatic number of a graph
zbMATH Open document ID: 0933.05051
DOI: 10.1016/S0166-218X(98)00146-2
author: Robert W. Irving
author: David F. Manlove
published in: Discrete Applied Mathematics
publication date: 1999-12-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1271069
zbMATH Keywords: achromatic number
zbMATH Keywords: independent sets
zbMATH Keywords: partition
zbMATH Keywords: b-chromatic number
zbMATH Keywords: NP-complete
zbMATH Keywords: characterization
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
cites work: Achromatic number is NP-complete for cographs and interval graphs
cites work: Q4364806
cites work: On the computational complexity of upper fractional domination
cites work: Some perfect coloring properties of graphs
cites work: Concerning the achromatic number of graphs
cites work: Q4198056
cites work: Approximating the minimum maximal independence number
cites work: Maximum versus minimum invariants for graphs
cites work: The achromatic number of a graph
cites work: Q5578801
cites work: Q3791195
cites work: Q3126442
cites work: On approximating the minimum independent dominating set
cites work: Edge Dominating Sets in Graphs
Wikidata QID: Q131685792
description: scientific article; zbMATH DE number 1271069