Unit-distance graphs in Minkowski metric spaces |
| |
Authors: | Kiran B Chilakamarri |
| |
Institution: | (1) Department of Mathematics, The Ohio State University, 43210 Columbus, Ohio, U.S.A. |
| |
Abstract: | The Unit-Distance Graph problem in Euclidean plane asks for the minimum number of colors, so that each point on the Euclidean plane can be assigned a single color with the condition that the points at unit distance apart are assigned different colors. It is well known that this number is between 4 and 7, but the exact value is not known. Here this problem is generalized to Minkowski metric spaces and once again the answer is shown to be between 4 and 7. In extreme special cases where the unit circle is a parallelogram or a hexagon the answer is shown to be exactly 4. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|