The b-chromatic number of a graph (Q1283791): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Achromatic number is NP-complete for cographs and interval graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4364806 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the computational complexity of upper fractional domination / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some perfect coloring properties of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Concerning the achromatic number of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4198056 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating the minimum maximal independence number / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum versus minimum invariants for graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The achromatic number of a graph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5578801 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3791195 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3126442 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On approximating the minimum independent dominating set / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edge Dominating Sets in Graphs / rank
 
Normal rank

Latest revision as of 18:14, 28 May 2024

scientific article
Language Label Description Also known as
English
The b-chromatic number of a graph
scientific article

    Statements

    The b-chromatic number of a graph (English)
    0 references
    0 references
    0 references
    16 December 1999
    0 references
    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.
    0 references
    achromatic number
    0 references
    independent sets
    0 references
    partition
    0 references
    b-chromatic number
    0 references
    NP-complete
    0 references
    characterization
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references