On Large Subgraphs with Small Chromatic Numbers Contained in Distance Graphs

被引：0
作者：
Kokotkin A. [1 ]
Raigorodskii A. [1 ]
机构：
[1] Moscow Institute of Physics and Technology, Moscow
来源：
Journal of Mathematical Sciences | 2016年 / 214卷 / 5期
关键词：
Random Graph; Chromatic Number; Probabilistic Result; Threshold Probability; Distance Graph;
D O I：
10.1007/s10958-016-2804-3
中图分类号：
学科分类号：
摘要：
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. © 2016, Springer Science+Business Media New York.
引用
收藏
页码：665 / 674
页数：9
相关论文
共 23 条
  • [1] Agarwal P.K., Pach J., Combinatorial Geometry, John Wiley and Sons Inc, Combinatorial Geometry, (1995)
  • [2] Alon N., Spencer J., The Probabilistic Method, (2000)
  • [3] Bollobas B., Random Graphs, (2001)
  • [4] Brass P., Moser W., Pach J., Research Problems in Discrete Geometry, Springer, Research Problems in Discrete Geometry, (2005)
  • [5] Coulson D., A 15-colouring of 3-space omitting distance one, Discrete Math., 256, pp. 83-90, (2002)
  • [6] Croft H.T., Incident incidents, Eureka, 30, pp. 22-26, (1967)
  • [7] de Bruijn N.G., Erdos P., A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet. Ser. A, 54, 5, pp. 371-373, (1951)
  • [8] Janson S., Luczak T., Rucinski A., Random Graphs, (2000)
  • [9] Klee V., Wagon S., Old and New Unsolved Problems in Plane Geometry and Number Theory, Math, (1991)
  • [10] Kolchin V.F., Random Graphs, (1999)
123