E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Mat. Sb., 2013, Volume 204, Number 4,Pages <nobr>49

This article is cited in 21 papers

Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size

E. E. Demekhin^a, A. M. Raigorodskii^ab, O. I. Rubanov^ab

^a M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
^b Moscow Institute of Physics and Technology (State University)

Abstract: It is established that there exist sequences of distance graphs $G_n\subset\mathbb R^n$, with chromatic numbers which grow exponentially, but, at the same time, without cliques or cycles of a given size.
Bibliography: 42 titles.

Keywords: distance graph, random graph, chromatic number, clique, cycle.

UDC: 519.112.4+519.174+519.176

MSC: 05C15, 05C35, 05D10

Received: 14.12.2010 and 09.12.2011

DOI: 10.4213/sm7830