Graph colourings and partitions (Q5941502)

From MaRDI portal
scientific article; zbMATH DE number 1635695
Language Label Description Also known as
English
Graph colourings and partitions
scientific article; zbMATH DE number 1635695

    Statements

    Graph colourings and partitions (English)
    0 references
    0 references
    20 August 2001
    0 references
    The author considers three coloring-related parameters of finite simple undirected graphs: the chromatic, achromatic and pseudochromatic numbers. The chromatic number is the minimum number of colors needed to color the vertices of \(G\) in such a way that adjacent vertices receive different colors. The achromatic number is the maximum size of a partition of the vertices of \(G\) into independent sets so that any two parts are adjacent. The pseudochromatic number is the maximum size of a partition of the vertices of \(G\) so that any two parts are adjacent. It is mentioned that the computation of any of the three parameters is NP-complete. These parameters are studied in terms of graph homomorphisms, epimorhisms and graph partitions. A relation fo the achromatic number and projective planes is given, and it is proved that different perfectness-related notions that are defined via the three parameters are equivalent. At last, some bounds are proved for the achromatic and pseudochromatic numbers and the pseudochromatic number of group graph \(G(N_n,D_1)\) is computed.
    0 references
    chromatic number
    0 references
    achromatic number
    0 references
    pseudoachromatic number
    0 references
    clique number
    0 references
    colourings
    0 references
    independent set
    0 references
    partitions
    0 references
    partition graph
    0 references
    perfect graphs
    0 references
    graphs
    0 references

    Identifiers