Achromatic numbers of Kneser graphs

Gabriela Araujo-Pardo, Juan Carlos Díaz-Patiño, Christian Rubio-Montiel


Complete vertex colorings have the property that any two color classes have at least an edge between them. Parameters such as the Grundy, achromatic and pseudoachromatic numbers come from complete colorings, with some additional requirement. In this paper, we estimate these numbers in the Kneser graph K(n, k) for some values of n and k. We give the exact value of the achromatic number of K(n, 2).


Achromatic number, pseudoachromatic number, Grundy number, block designs, geometric type Kneser graphs

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications