Coloring Some Finite Sets in ℝn
This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-03-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1641 |
| _version_ | 1797704403504857088 |
|---|---|
| author | Balogh József Kostochka Alexandr Raigorodskii Andrei |
| author_facet | Balogh József Kostochka Alexandr Raigorodskii Andrei |
| author_sort | Balogh József |
| collection | DOAJ |
| description | This note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1. |
| first_indexed | 2024-03-12T05:19:51Z |
| format | Article |
| id | doaj.art-88f465e722df4052b6aa780a422f757c |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:19:51Z |
| publishDate | 2013-03-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-88f465e722df4052b6aa780a422f757c2023-09-03T07:47:22ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-03-01331253110.7151/dmgt.1641Coloring Some Finite Sets in ℝnBalogh József0Kostochka Alexandr1Raigorodskii Andrei2Department of Mathematics, University of Illinois, Urbana, IL 61801, USADepartment of Mathematics, University of Illinois, Urbana, IL, 61801, USA, Sobolev Institute of Mathematics, Novosibirsk, RussiaDepartment of Mechanics and Mathematics, Moscow State University, Leninskie gory, Moscow, 119991, Russia Department of Discrete Mathematics, Moscow Institute of Physics and Technology, Dolgoprudny, RussiaThis note relates to bounds on the chromatic number χ(ℝn) of the Euclidean space, which is the minimum number of colors needed to color all the points in ℝn so that any two points at the distance 1 receive different colors. In [6] a sequence of graphs Gn in ℝn was introduced showing that . For many years, this bound has been remaining the best known bound for the chromatic numbers of some lowdimensional spaces. Here we prove that and find an exact formula for the chromatic number in the case of n = 2k and n = 2k − 1.https://doi.org/10.7151/dmgt.1641chromatic numberindependence numberdistance graph |
| spellingShingle | Balogh József Kostochka Alexandr Raigorodskii Andrei Coloring Some Finite Sets in ℝn Discussiones Mathematicae Graph Theory chromatic number independence number distance graph |
| title | Coloring Some Finite Sets in ℝn |
| title_full | Coloring Some Finite Sets in ℝn |
| title_fullStr | Coloring Some Finite Sets in ℝn |
| title_full_unstemmed | Coloring Some Finite Sets in ℝn |
| title_short | Coloring Some Finite Sets in ℝn |
| title_sort | coloring some finite sets in rn |
| topic | chromatic number independence number distance graph |
| url | https://doi.org/10.7151/dmgt.1641 |
| work_keys_str_mv | AT baloghjozsef coloringsomefinitesetsinrn AT kostochkaalexandr coloringsomefinitesetsinrn AT raigorodskiiandrei coloringsomefinitesetsinrn |