2015/09/11 by James D. Currie, Currie, James D., Roger B. Eggleton +1
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Mathematics and Applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1509.03667
openalex publication_date 2015/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be the unit distance graph in the plane. A well-known problem in combinatorial geometry is that of determining the chromatic number of G. It is known that 4≤ χ(G)≤ 7. The upper bound of 7 is obtained using tilings of the plane. The present paper studies two problems where we seek proper colourings of G, adding restrictions inspired by tilings: Let H(ε) be the graph whose vertices are the points of \mathbb R2, with an edge between two points if their distance lies in the interval [1,1+ε]. We show that for small ε, 0