On large subgraphs of a distance graph which have small chromatic number (Q2342369): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 17:06, 2 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On large subgraphs of a distance graph which have small chromatic number |
scientific article |
Statements
On large subgraphs of a distance graph which have small chromatic number (English)
0 references
11 May 2015
0 references
In the paper, some results on distance graphs in two-dimensional Euclidean space are presented without proofs. Vertices in a distance graph correspond to points in the plane, and two vertices are adjacent if their Euclidean distance is equal to \(1\). The chromatic number of the plane is defined as a maximum of chromatic numbers of distance graphs realized in the plane. The first result estimates the number of vertices in an induced subgraph \(G'\) with chromatic number \(\chi (G')=k\) of any distance graph \(G\) on \(n\) vertices in the plane. In the next two results, the author presents estimations of the threshold probability for the realization of a random graph \(G(n,p)\) as a distance graph in the plane. \[ \frac{1-\epsilon}{n} \leq p^*(n) \leq \frac{t_0 +\epsilon}{n} \] where \(t_0 = 14.797\). The threshold probability \(p^* (n)\) is defined as \[ p^* (n) = \sup\{ p\in [0,1] : P_n (G\text{ can be realized as a distance graph in the plane})>1/2\} \]
0 references
distance graph
0 references
chromatic number
0 references
random graph
0 references