Geodesic
On large subgraphs with small chromatic numbers contained in distance graphs
Contemporary Mathematics. Fundamental Directions, Topology, Tome 51 (2013), pp. 64-73

Voir la notice de l'article provenant de la source Math-Net.Ru

It is proved that each distance graph on a plane has an induced subgraph with a chromatic number that is at most 4 containing over 91 % of the vertices of the original graph. This result is used to obtain the asymptotic growth rate for a threshold probability that a random graph is isomorphic to a certain distance graph on a plane. Several generalizations to larger dimensions are proposed. 
@article{CMFD_2013_51_a3,
     author = {A. A. Kokotkin and A. M. Raigorodskii},
     title = {On large subgraphs with small chromatic numbers contained in distance graphs},
     journal = {Contemporary Mathematics. Fundamental Directions},
     pages = {64--73},
     publisher = {mathdoc},
     volume = {51},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CMFD_2013_51_a3/}
}
TY  - JOUR
AU  - A. A. Kokotkin
AU  - A. M. Raigorodskii
TI  - On large subgraphs with small chromatic numbers contained in distance graphs
JO  - Contemporary Mathematics. Fundamental Directions
PY  - 2013
SP  - 64
EP  - 73
VL  - 51
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMFD_2013_51_a3/
LA  - ru
ID  - CMFD_2013_51_a3
ER  - 
%0 Journal Article
%A A. A. Kokotkin
%A A. M. Raigorodskii
%T On large subgraphs with small chromatic numbers contained in distance graphs
%J Contemporary Mathematics. Fundamental Directions
%D 2013
%P 64-73
%V 51
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMFD_2013_51_a3/
%G ru
%F CMFD_2013_51_a3
A. A. Kokotkin; A. M. Raigorodskii. On large subgraphs with small chromatic numbers contained in distance graphs. Contemporary Mathematics. Fundamental Directions, Topology, Tome 51 (2013), pp. 64-73. http://geodesic.mathdoc.fr/item/CMFD_2013_51_a3/