A. M. Raigorodskii, M. Koshelev, “New bounds for the clique-chromatic numbers of Johnson graphs”, Dokl. RAN. Math. Inf. Proc. Upr., 2020, Volume 490,Pages <nobr>78

This article is cited in 10 papers

INFORMATICS

New bounds for the clique-chromatic numbers of Johnson graphs

A. M. Raigorodskii^abcd, M. Koshelev^a

^a Lomonosov Moscow State University, Moscow, Russian Federation
^b Moscow Institute of Physics and Technology (National Research University), Dolgoprudny, Moscow Region, Russian Federation
^c Caucasus Mathematical Center, Adyghe State University, Maykop, Russian Federation
^d Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude, Russian Federation

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.

UDC: 519

Presented: V. V. Kozlov
Received: 27.07.2019
Revised: 27.07.2019
Accepted: 01.11.2019

DOI: 10.31857/S268695432001018X