Coloring distance graphs on the plane. (English) Zbl 1514.05057
Summary: We consider the coloring of certain distance graphs on the Euclidean plane. Namely, we ask for the minimal number of colors needed to color all points of the plane in such a way that pairs of points at distance in the interval \([1, b]\) get different colors. The classic Hadwiger-Nelson problem is a special case of this question – obtained by taking \(b = 1\). The main results of the paper are improved lower and upper bounds on the number of colors for some values of \(b\). In particular, we determine the minimal number of colors for two ranges of values of \(b\) – one of which is enlarging an interval presented by G. Exoo [Discrete Comput. Geom. 33, No. 1, 117–123 (2005; Zbl 1055.05048)] and the second is completely new. Up to our knowledge, these are the only known families of distance graphs on \(\mathbb{R}^2\) with a determined nontrivial finite chromatic number. Moreover, we present the first 8-coloring for \(b\) larger than values of \(b\) for the known 7-colorings. As a byproduct, we give some bounds and exact values for bounded parts of the plane, specifically by coloring certain annuli.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C12 | Distance in graphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 1055.05048References:
| [1] | Ágoston, P.; Pálvölgyi, D., Comments of Pálvölgyi in Polymath16, thread 14, comments 24460 and 24487 (2019) |
| [2] | Alm, J. F.; Manske, J., On radial colorings of annuli, Australas. J. Comb., 60, 270-278 (2014) · Zbl 1305.05067 |
| [3] | Ardal, H.; Maňuch, J.; Rosenfeld, M.; Shelah, S.; Stacho, L., The odd-distance plane graph, Discrete Comput. Geom., 42, 2, 132-141 (Sep 2009) · Zbl 1200.05059 |
| [4] | Axenovich, M.; Choi, J.; Lastrina, M.; McKay, T.; Smith, J.; Stanton, B., On the chromatic number of subsets of the euclidean plane, Graphs Comb., 30, 1, 71-81 (2014) · Zbl 1292.05096 |
| [5] | Bauslaugh, B. L., Tearing a strip off the plane, J. Graph Theory, 29, 1, 17-33 (1998) · Zbl 0919.05018 |
| [6] | Bellitto, T.; Pêcher, A.; Sédillot, A., On the density of sets of the Euclidean plane avoiding distance 1, Discret. Math. Theor. Comput. Sci., 23, 1 (Aug. 2021) · Zbl 1498.05078 |
| [7] | Bock, F., Epsilon-colorings of strips, Acta Math. Univ. Comen., 88, 3, 469-473 (2019) |
| [8] | Brown, N.; Dunfield, N.; Perry, G., Colorings of the plane (1992), preprint |
| [9] | Bukh, B., Measurable sets with excluded distances, Geom. Funct. Anal., 18, 3, 668-697 (2008) · Zbl 1169.52005 |
| [10] | Cherkashin, D.; Kulikov, A.; Raigorodskii, A., On the chromatic numbers of small-dimensional euclidean spaces, Discrete Appl. Math., 243, 125-131 (2018) · Zbl 1387.05061 |
| [11] | Cranston, D. W.; Rabern, L., The fractional chromatic number of the plane, Combinatorica, 37, 5, 837-861 (2017) · Zbl 1399.05069 |
| [12] | Currie, J. D., Connectivity of distance graphs, Discrete Math., 1, 91-94 (1992) · Zbl 0777.05058 |
| [13] | Currie, J. D.; Eggleton, R. B., Chromatic properties of the euclidean plane, Preprint |
| [14] | Davies, J., Odd distances in colourings of the plane (2022), Preprint |
| [15] | de Bruijn, N. G.; Erdős, P., A colour problem for infinite graphs and a problem in the theory of relations, 13, 369-373 (1951) · Zbl 0044.38203 |
| [16] | de Grey, A., The chromatic number of the plane is at least 5, Geombinatorics, 28, 18-31 (2018) · Zbl 1404.05063 |
| [17] | DeVos, M.; Ebrahimi, J.; Ghebleh, M.; Goddyn, L.; Mohar, B.; Naserasr, R., Circular coloring the plane, SIAM J. Discrete Math., 21, 461-465 (2007) · Zbl 1140.05303 |
| [18] | Dunfield, N.; Brown, N.; Perry, G., Colorings of the plane i, Geombinatorics, III, 24-31 (1993) · Zbl 0846.05030 |
| [19] | Dunfield, N.; Brown, N.; Perry, G., Colorings of the plane ii, Geombinatorics, III, 64-74 (1994) · Zbl 0846.05031 |
| [20] | Dunfield, N.; Brown, N.; Perry, G., Colorings of the plane iii, Geombinatorics, III, 110-114 (1994) · Zbl 0846.05032 |
| [21] | Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring the real line, J. Comb. Theory, Ser. B, 39, 1, 86-100 (1985) · Zbl 0549.05029 |
| [22] | Eggleton, R. B.; Erdős, P.; Skilton, D. K., Colouring prime distance graphs, Graphs Comb., 6, 1, 17-32 (1990) · Zbl 0698.05033 |
| [23] | Exoo, G., ε-unit distance graphs, Discrete Comput. Geom., 33, 117-123 (2005) · Zbl 1055.05048 |
| [24] | Exoo, G.; Ismailescu, D., On the chromatic number of \(\mathbb{R}^n\) for small values of n (2014), Preprint |
| [25] | Exoo, G.; Ismailescu, D., A unit distance graph in the plane with fractional chromatic number 383/102, Geombinatorics, 26, 3, 122-127 (2017) · Zbl 1360.05032 |
| [26] | Exoo, G.; Ismailescu, D., The Hadwiger-Nelson problem with two forbidden distances, Geombinatorics, 28, 51-68 (2018) · Zbl 1407.05072 |
| [27] | Exoo, G.; Ismailescu, D., The chromatic number of the plane is at least 5: a new proof, Discrete Comput. Geom., 1-11 (2019) |
| [28] | Exoo, G.; Ismailescu, D., A 6-chromatic two-distance graph in the plane, Geombinatorics, 29, 3 (2020) · Zbl 1452.05048 |
| [29] | Exoo, G.; Ismailescu, D.; Lim, M., On the chromatic number of \(\mathbb{R}^4\), Discrete Comput. Geom., 52, 2, 416-423 (2014) · Zbl 1302.05051 |
| [30] | Falconer, K., The realization of distances in measurable subsets covering \(\mathbb{R}^n\), J. Comb. Theory, Ser. A, 31, 2, 184-189 (1981) · Zbl 0469.05021 |
| [31] | Fürstenberg, H.; Katznelson, Y.; Weiss, B., Ergodic Theory and Configurations in Sets of Positive Density, 184-198 (1990), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 0738.28013 |
| [32] | Grytczuk, J.; Junosza-Szaniawski, K.; Lonc, Z., Colouring \((a, b)\)-distance graphs, (Talk on Colourings, Independence and Domination - Workshop on Graph Theory. Talk on Colourings, Independence and Domination - Workshop on Graph Theory, Karpacz (2007)) |
| [33] | Grytczuk, J.; Junosza-Szaniawski, K.; Sokół, J.; Węsek, K., Fractional and j-fold coloring of the plane, Discrete Comput. Geom., 55, 594-609 (2016) · Zbl 1338.05082 |
| [34] | Hadwiger, H., Überdeckung des euklidischen raum durch kongruente mengen, Port. Math., 4, 238-242 (1945) · Zbl 0060.40611 |
| [35] | Hadwiger, H., Ungeloste probleme, Elem. Math., 16, 103-104 (1961) · Zbl 0118.17302 |
| [36] | Heule, M. J.H., Computing small unit-distance graphs with chromatic number 5, Geombinatorics, 28, 32-50 (2018) · Zbl 1404.05054 |
| [37] | Heule, M. J.H., Searching for a unit-distance graph with chromatic number 6, (Heule, M. J.H.; Järvisalo, M.; Suda, M., SAT COMPETITION 2018 (2018), University of Helsinki), 66 |
| [38] | Heule, M. J.H., Trimming graphs using clausal proof optimization, (Schiex, T.; de Givry, S., Principles and Practice of Constraint Programming (2019), Springer International Publishing), 251-267 |
| [39] | Ivanov, L. L., On the chromatic numbers of \(\mathbb{R}^2\) and \(\mathbb{R}^3\) with intervals of forbiden distances, Electron. Notes Discrete Math., 29, 159-162 (2007) · Zbl 1341.05052 |
| [40] | Parts, J., Comments in polymath16, thread 12, comment 23601 (2019) |
| [41] | Junosza-Szaniawski, K., Upper bound on the circular chromatic number of the plane, Electron. J. Comb., 25, 1, 1-53 (2018) · Zbl 1391.05110 |
| [42] | Kanel-Belov, A.; Voronov, V.; Cherkashin, D., On the chromatic number of an infinitesimal plane layer, St. Petersburg Math. J., 29, 5, 761-775 (2018) · Zbl 1393.05117 |
| [43] | Katz, R.; Krebs, M.; Shaheen, A., Zero sums on unit square vertex sets and plane colorings, Am. Math. Mon., 121, 7, 610-618 (2014) · Zbl 1306.05064 |
| [44] | Katznelson, Y., Chromatic numbers of Cayley graphs on \(\mathbb{Z}\) and recurrence, Combinatorica, 21, 2, 211-219 (2001) · Zbl 0981.05038 |
| [45] | Kloeckner, B. R., Coloring distance graphs: a few answers and many questions, Geombinatorics, 24, 117-134 (2015) · Zbl 1334.05039 |
| [46] | Koch, T., Rapid Mathematical Prototyping (2004), Technische Universität Berlin, PhD thesis |
| [47] | Krebs, M., Finite ϵ-unit distance graphs, J. Algebra Comb. Discret. Struct. Appl., 8, 161-166 (2021) · Zbl 1482.05112 |
| [48] | Kruskal, C. P., The chromatic number of the plane: the bounded case, J. Comput. Syst. Sci., 74, 4, 598-627 (2008) · Zbl 1139.05023 |
| [49] | Nielsen, M. J., Solution to problem 10, Can. Math. Bull., 4, 187-189 (1961) |
| [50] | Oostema, P.; Martins, R.; Heule, M., Coloring unit-distance strips using sat, (Albert, E.; Kovacs, L., LPAR23. LPAR-23: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning. LPAR23. LPAR-23: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, EPiC Series in Computing, vol. 73 (2020), EasyChair), 373-389 |
| [51] | Owings, J.; Tetiva, M.; Huddleston, M., Coloring the plane, Am. Math. Mon., 115, 2, 170-172 (2008) |
| [52] | Parts, J., A small 6-chromatic two-distance graph in the plane, Geombinatorics, 29, 3, 111-115 (2020) · Zbl 1458.05082 |
| [53] | Parts, J., Graph minimization, focusing on the example of 5-chromatic unit-distance graphs in the plane, Geombinatorics, 29, 4, 137 (2020) · Zbl 1452.05070 |
| [54] | Parts, J., The chromatic number of the plane is at least 5 a human-verifiable proof, Geombinatorics, 29, 2, 77-102 (2020) · Zbl 1455.05020 |
| [55] | Parts, J., What percent of the plane can be properly 5- and 6-colored?, Geombinatorics, 30, 1, 25-40 (2020) · Zbl 1452.05069 |
| [56] | Parts, J., A 6-chromatic odd-distance graph in the plane, Geombinatorics, 31, 4, 124-137 (2022) · Zbl 1505.05056 |
| [57] | Parts, J., On upper bounds for the multi-fold chromatic numbers of the plane, Geombinatorics, 30, 4, 177-189 (2021) · Zbl 1466.05077 |
| [58] | Payne, M. S., Unit distance graphs with ambiguous chromatic number, Electron. J. Comb., 16, 1, 1-7 (2009) · Zbl 1185.05063 |
| [59] | Perz, D., Triangles in the colored Euclidean plane (2018), Graz University of Technology, Master’s thesis |
| [60] | Polymath Project · Zbl 1315.01078 |
| [61] | Pritikin, D., All unit-distance graphs of order 6197 are 6-colorable, J. Comb. Theory, Ser. B, 73, 2, 159-163 (1998) · Zbl 0920.05027 |
| [62] | Ruzsa, I. Z.; Tuza, Z.; Voigt, M., Distance graphs with finite chromatic number, J. Comb. Theory, Ser. B, 85, 1, 181-187 (2002) · Zbl 1027.05036 |
| [63] | Scheinerman, E. R.; Ullman, D. H., Fractional Graph Theory: a Rational Approach to the Theory of Graphs (2011), Courier Corporation · Zbl 1254.05003 |
| [64] | Shelah, S.; Soifer, A., Axiom of choice and chromatic number of the plane, J. Comb. Theory, Ser. A, 103, 2, 387-391 (2003) · Zbl 1030.03035 |
| [65] | Shelah, S.; Soifer, A., Axiom of choice and chromatic number: examples on the plane, J. Comb. Theory, Ser. A, 105, 2, 359-364 (2004) · Zbl 1057.03036 |
| [66] | Soifer, A., Axiom of choice and chromatic number of \(\mathbb{R}^n\), J. Comb. Theory, Ser. A, 110, 1, 169-173 (2005) · Zbl 1063.03035 |
| [67] | Soifer, A., The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators (2009), Springer-Verlag: Springer-Verlag New York · Zbl 1221.05001 |
| [68] | Steinhardt, J., On coloring the odd-distance graph, Electron. J. Comb., 16, 12 (2009) · Zbl 1197.05060 |
| [69] | Townsend, S. P., Every 5-colouring map in the plane contains a monochrome unit, J. Comb. Theory, Ser. A, 30, 114-115 (1979) · Zbl 0458.05032 |
| [70] | Townsend, S. P., Colouring the plane with no monochrome unit, Geombinatorics, XIV, 181-193 (2005) · Zbl 1506.05079 |
| [71] | Voronov, V.; Neopryatnaya, A.; Dergachev, E., Constructing 5-chromatic unit distance graphs embedded in the Euclidean plane and two-dimensional spheres (2021), Preprint · Zbl 1497.05101 |
| [72] | Walczak, Z.; Wojciechowski, J. M., Transmission scheduling in packet radio networks using graph coloring algorithm, (2006 International Conference on Wireless and Mobile Communications (ICWMC’06) (2006)), 46 |
| [73] | Williams, H. P.; Yan, H., Representations of the all_different predicate of constraint satisfaction in integer programming, INFORMS J. Comput., 13, 2, 96-103 (2001) · Zbl 1238.90103 |
| [74] | Woodall, D. R., Distances realized by sets covering the plane, J. Comb. Theory, Ser. A, 14, 187-200 (1973) · Zbl 0251.50003 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
