Research Article
BibTex RIS Cite
Year 2021, Volume: 8 Issue: 3, 161 - 166, 15.09.2021
https://doi.org/10.13069/jacodesmath.1000784

Abstract

References

  • [1] J. D. Currie and R. B. Eggleton, Chromatic properties of the Euclidean plane, arXiv:1509.03667 11 Sep 2015.
  • [2] G. Exoo, $\epsilon$-unit distance graphs, Discrete Comput. Geom. 33(1) (2005) 117-123.
  • [3] K. J. Falconer, The realization of distances in measurable subsets covering Rn, J. Combin. Theory Ser. A 31(2) (1981) 184-189.
  • [4] A. D. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28(1) (2018) 18–31.
  • [5] J. Grytczuk, K. Junosza-Szaniawski, J. Sokół, K. Wesek, Fractional and j-fold coloring of the plane, Discrete Comput. Geom. 55(3) (2016) 594-609.
  • [6] M. J. Nielsen, Approximating monochromatic triangles in a two-colored plane, Acta Math. Hungar. 74(4) (1997) 279-286.
  • [7] A. Soifer, The mathematical coloring book, Springer, New York (2009).

Finite $\epsilon$-unit distance graphs

Year 2021, Volume: 8 Issue: 3, 161 - 166, 15.09.2021
https://doi.org/10.13069/jacodesmath.1000784

Abstract

In 2005, Exoo posed the following question. Fix $\epsilon$ with $0\leq\epsilon<1$. Let $G_\epsilon$ be the graph whose vertex set is the Euclidean plane, where two vertices are adjacent iff the Euclidean distance between them lies in the closed interval $[1-\epsilon,1+\epsilon]$. What is the chromatic number $\chi(G_\epsilon)$ of this graph? The case $\epsilon=0$ is precisely the classical ``chromatic number of the plane'' problem. In a 2018 preprint, de Grey shows that $\chi(G_0)\geq 5$; the proof relies heavily on machine computation. In 2016, Grytczuk et al. proved a weaker result with a human-comprehensible but nonconstructive proof: whenever $0<\epsilon<1$, we have that $\chi(G_\epsilon)\geq 5$. (This lower bound of $5$ was later improved by Currie and Eggleton to $6$.) The De Bruijn - Erd\H{o}s theorem (which relies on the axiom of choice) then guarantees the existence, for each $\epsilon$, of a finite subgraph $H_\epsilon$ of $G_\epsilon$ such that $\chi(H_\epsilon)\geq 5$. In this paper, we explicitly construct such finite graphs $H_\epsilon$. We find that the number of vertices needed to create such a graph is no more than $2\pi(15+14\epsilon^{-1})^2$. Our proof can be done by hand without the aid of a computer.

References

  • [1] J. D. Currie and R. B. Eggleton, Chromatic properties of the Euclidean plane, arXiv:1509.03667 11 Sep 2015.
  • [2] G. Exoo, $\epsilon$-unit distance graphs, Discrete Comput. Geom. 33(1) (2005) 117-123.
  • [3] K. J. Falconer, The realization of distances in measurable subsets covering Rn, J. Combin. Theory Ser. A 31(2) (1981) 184-189.
  • [4] A. D. de Grey, The chromatic number of the plane is at least 5, Geombinatorics 28(1) (2018) 18–31.
  • [5] J. Grytczuk, K. Junosza-Szaniawski, J. Sokół, K. Wesek, Fractional and j-fold coloring of the plane, Discrete Comput. Geom. 55(3) (2016) 594-609.
  • [6] M. J. Nielsen, Approximating monochromatic triangles in a two-colored plane, Acta Math. Hungar. 74(4) (1997) 279-286.
  • [7] A. Soifer, The mathematical coloring book, Springer, New York (2009).
There are 7 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Mike Krebs This is me 0000-0002-5097-2647

Early Pub Date October 9, 2021
Publication Date September 15, 2021
Published in Issue Year 2021 Volume: 8 Issue: 3

Cite

APA Krebs, M. (2021). Finite $\epsilon$-unit distance graphs. Journal of Algebra Combinatorics Discrete Structures and Applications, 8(3), 161-166. https://doi.org/10.13069/jacodesmath.1000784
AMA Krebs M. Finite $\epsilon$-unit distance graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. September 2021;8(3):161-166. doi:10.13069/jacodesmath.1000784
Chicago Krebs, Mike. “Finite $\epsilon$-Unit Distance Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 8, no. 3 (September 2021): 161-66. https://doi.org/10.13069/jacodesmath.1000784.
EndNote Krebs M (September 1, 2021) Finite $\epsilon$-unit distance graphs. Journal of Algebra Combinatorics Discrete Structures and Applications 8 3 161–166.
IEEE M. Krebs, “Finite $\epsilon$-unit distance graphs”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 8, no. 3, pp. 161–166, 2021, doi: 10.13069/jacodesmath.1000784.
ISNAD Krebs, Mike. “Finite $\epsilon$-Unit Distance Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications 8/3 (September 2021), 161-166. https://doi.org/10.13069/jacodesmath.1000784.
JAMA Krebs M. Finite $\epsilon$-unit distance graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2021;8:161–166.
MLA Krebs, Mike. “Finite $\epsilon$-Unit Distance Graphs”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 8, no. 3, 2021, pp. 161-6, doi:10.13069/jacodesmath.1000784.
Vancouver Krebs M. Finite $\epsilon$-unit distance graphs. Journal of Algebra Combinatorics Discrete Structures and Applications. 2021;8(3):161-6.