This article is cited in 9 papers

New Upper Bound for the Chromatic Numberof a Random Subgraph of a Distance Graph

A. S. Gusev


Abstract: This paper is related to the classical Hadwiger–Nelson problem dealing with the chromatic numbers of distance graphs in ${\mathbb R}^n$. We consider the class consisting of the graphs $G(n,2s+1,s)=(V(n,2s+1), E(n,2s+1,s))$ defined as follows:
\begin{align*} V(n,2s+1)&=\{x=(x_1,x_2,\dots,x_n): x_i\in \{0,1\}, \, x_1+x_2+\dots+x_n=2s+1\}, \\ E(n,2s+1,s)&=\{\{x,y\}:(x,y)=s\}, \end{align*}
where $(x,y)$ stands for the inner product. We study the random graph ${\mathcal G}(G(n,2s+1,s),p)$ each of whose edges is taken from the set $E(n,2s+1,s)$ with probability $p$ independently of the other edges. We prove a new bound for the chromatic number of such a graph.

Keywords: Hadwiger–Nelson problem, distance graph, random subgraph, chromatic number, Turán number.

UDC: 519.174

Received: 10.08.2014

DOI: 10.4213/mzm10550

 English version: Mathematical Notes, 2015, 97:3, 326–332

Bibliographic databases:

• 
• 
• 
• 
•