New Bounds for the Clique-Chromatic Numbers of Johnson Graphs

A. M. Raigorodskii^a^,^b^,^c^,^d^,* and M. M. Koshelev^b^,**

^aMoscow Institute of Physics and Technology (National Research University), Dolgoprudnyi, Moscow oblast, 141700 Russia

^bFaculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, 119991 Russia

^cCaucasus Mathematical Center, Adyghe State University, Maykop, 385000 Republic of Adygea, Russia

^d Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude, 670000 Buryat Republic, Russia

Correspondence to: *e-mail: mraigor@yandex.ru
Correspondence to: **e-mail: mkoshelev99@gmail.com

Received 27 July, 2019

Abstract—We significantly improve lower bounds on the clique-chromatic numbers for some families of Johnson graphs. A new upper bound on the clique-chromatic numbers for G(n, r, r – 1) and G(n, 3, 1) is obtained. Finally, the exact value of the clique-chromatic number for G(n, 2, 1) is provided.

Keywords: clique-chromatic numbers, Johnson graphs, Ramsey numbers

DOI: 10.1134/S1064562420010184