New Upper Bound for the Chromatic Number\\ of a~Random Subgraph of a~Distance Graph

A. S. Gusev

Matematičeskie zametki, Tome 97 (2015) no. 3, pp. 342-349

Résumé

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.

Détail

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