Colour number, capacity, and perfectness of directed graphs (Q5935600)

From MaRDI portal
Revision as of 00:38, 30 January 2024 by Import240129110155 (talk | contribs) (Added link to MaRDI item.)
scientific article; zbMATH DE number 1610694
Language Label Description Also known as
English
Colour number, capacity, and perfectness of directed graphs
scientific article; zbMATH DE number 1610694

    Statements

    Colour number, capacity, and perfectness of directed graphs (English)
    0 references
    0 references
    0 references
    26 June 2001
    0 references
    The authors introduce a variant of the chromatic number for a directed graph \(G\), called the colour number: the minimum, over all partitions of \(V(G)\), of the sum (taken over all subsets of the partition) of the quantities: 1 plus the maximum outdegree of the directed graph induced by a given subset. This parameter is used to upper-bound the transitive clique number and the Sperner capacity of arbitrary directed graphs. The results give a common generalization of previously known bounds and lead to a concept of perfectness for a directed graph: the colour number and the transitive clique number agree, for each induced subgraph.
    0 references
    chromatic number
    0 references
    colour number
    0 references
    clique number
    0 references
    Sperner capacity
    0 references
    perfectness
    0 references
    directed graph
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references