Geodesic
On large subgraphs with small chromatic numbers contained in distance graphs
Contemporary Mathematics. Fundamental Directions, Topology, Tome 51 (2013), pp. 64-73 
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/
@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},
     year = {2013},
     volume = {51},
     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
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
%U http://geodesic.mathdoc.fr/item/CMFD_2013_51_a3/
%G ru
%F CMFD_2013_51_a3

Voir la notice du chapitre de livre 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.

[1] Kolchin V. F., Sluchainye grafy, Fizmatlit, M., 2002

[2] Kupavskii A. B., Raigorodskii A. M., Titova M. V., “O plotneishikh mnozhestvakh bez rasstoyaniya edinitsa v prostranstvakh malykh razmernostei”, Tr. MFTI, 4:1 (2012), 91–110

[3] Raigorodskii A. M., “Problema Borsuka i khromaticheskie chisla metricheskikh prostranstv”, Usp. mat. nauk, 56:1 (2001), 107–146 | DOI | MR | Zbl

[4] Raigorodskii A. M., “O khromaticheskom chisle prostranstva”, Usp. mat. nauk, 55:2 (2000), 147–148 | DOI | MR | Zbl

[5] Raigorodskii A. M., Khromaticheskie chisla, MTsNMO, M., 2003

[6] Raigorodskii A. M., Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007 | Zbl

[7] Raigorodskii A. M., Modeli sluchainykh grafov, MTsNMO, M., 2011

[8] Soifer A., “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Mat. prosvesch. Ser. 3, 8, 2004

[9] Agarwal P. K., Pach J., Combinatorial geometry, John Wiley and Sons Inc., New York, 1995 | MR

[10] Alon N., Spencer J., The probabilistic method, Wiley-Interscience Ser. Discr. Math. Optim., 2000 | MR

[11] Bollobás B., Random graphs, Cambridge Univ. Press, 2001 | MR | Zbl

[12] Brass P., Moser W., Pach J., Research problems in discrete geometry, Springer, 2005 | MR

[13] Coulson D., “A 15-colouring of 3-space omitting distance one”, Discrete Math., 256 (2002), 83–90 | DOI | MR | Zbl

[14] Croft H. T., “Incident incidents”, Eureka (Cambridge), 30 (1967), 22–26

[15] De Bruijn N. G., Erdős P., “A colour problem for infinite graphs and a problem in the theory of relations”, Proc. Koninkl. Nederl. Acad. Wet. Ser. A, 54:5 (1951), 371–373 | Zbl

[16] Janson S., Luczak T., Ruciński A., Random graphs, Wiley, New York, 2000 | MR | Zbl

[17] Klee V., Wagon S., Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991 | MR | Zbl

[18] Larman D. G., Rogers C. A., “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[19] Nechushtan O., “Note on the space chromatic number”, Discrete Math., 256 (2002), 499–507 | DOI | MR | Zbl

[20] Soifer A., The mathematical coloring book, Springer, 2009 | MR

[21] Székely L. A., Erdős P., “On unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his Mathematics, v. II, Bolyai Soc. Math. Stud., 11, J. Bolyai Math. Soc., Springer, 2002, 649–666 | MR | Zbl