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)

← 1 2 3 →