|
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 Rn. 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: V(n,2s+1)={x=(x1,x2,…,xn):xi∈{0,1},x1+x2+⋯+xn=2s+1},E(n,2s+1,s)={{x,y}:(x,y)=s}, where (x,y) stands for the inner product. We study the random graph 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: | 454 | Full-text PDF : | 212 | References: | 82 | First page: | 45 |
|