Araştırma Makalesi
BibTex RIS Kaynak Göster
Yıl 2021, , 161 - 166, 15.09.2021
https://doi.org/10.13069/jacodesmath.1000784

Öz

Kaynakça

  • [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

Yıl 2021, , 161 - 166, 15.09.2021
https://doi.org/10.13069/jacodesmath.1000784

Öz

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.

Kaynakça

  • [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).
Toplam 7 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Mühendislik
Bölüm Makaleler
Yazarlar

Mike Krebs Bu kişi benim 0000-0002-5097-2647

Yayımlanma Tarihi 15 Eylül 2021
Yayımlandığı Sayı Yıl 2021

Kaynak Göster

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. Eylül 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, sy. 3 (Eylül 2021): 161-66. https://doi.org/10.13069/jacodesmath.1000784.
EndNote Krebs M (01 Eylül 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, c. 8, sy. 3, ss. 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 (Eylül 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, c. 8, sy. 3, 2021, ss. 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.