|
This article is cited in 8 scientific papers (total in 8 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.
Received: 10.08.2014
Citation:
A. S. Gusev, “New Upper Bound for the Chromatic Numberof a Random Subgraph of a Distance Graph”, Mat. Zametki, 97:3 (2015), 342–349; Math. Notes, 97:3 (2015), 326–332
Linking options:
https://www.mathnet.ru/eng/mzm10550https://doi.org/10.4213/mzm10550 https://www.mathnet.ru/eng/mzm/v97/i3/p342
|
Statistics & downloads: |
Abstract page: | 408 | Full-text PDF : | 185 | References: | 66 | First page: | 45 |
|