Graph colourings and partitions (Q5941502)

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.