Coloring distance graphs on the plane

被引:1
作者
Chybowska-Sokol, Joanna [1 ]
Junosza-Szaniawski, Konstanty [1 ]
Wesek, Krzysztof [1 ]
机构
[1] Warsaw Univ Technol, Fac Math & Informat Sci, Koszytkowa 75, PL-00662 Warsaw, Poland
关键词
Coloring; Distance graphs; Hadwiger-Nelson problem; CHROMATIC NUMBER; CHOICE; AXIOM; SUBSETS; SETS;
D O I
10.1016/j.disc.2023.113441
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider the coloring of certain distance graphs on the Euclidean plane. Namely, we ask for the minimal number of colors needed to color all points of the plane in such a way that pairs of points at distance in the interval [1, b] get different colors. The classic Hadwiger-Nelson problem is a special case of this question - obtained by taking b = 1. The main results of the paper are improved lower and upper bounds on the number of colors for some values of b. In particular, we determine the minimal number of colors for two ranges of values of b - one of which is enlarging an interval presented by Exoo and the second is completely new. Up to our knowledge, these are the only known families of distance graphs on R2 with a determined nontrivial finite chromatic number. Moreover, we present the first 8-coloring for b larger than values of b for the known 7-colorings. As a byproduct, we give some bounds and exact values for bounded parts of the plane, specifically by coloring certain annuli.(c) 2023 Elsevier B.V. All rights reserved.
引用
收藏
页数:15
相关论文
共 50 条
  • [41] On backbone coloring of graphs
    Wang, Weifan
    Bu, Yuehua
    Montassier, Mickael
    Raspaud, Andre
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2012, 23 (01) : 79 - 93
  • [42] Equitable Δ-coloring of graphs
    Chen, Bor-Liang
    Yen, Chih-Hung
    [J]. DISCRETE MATHEMATICS, 2012, 312 (09) : 1512 - 1517
  • [43] Coloring lines and Delaunay graphs with respect to boxes
    Tomon, Istvan
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2024, 64 (03) : 645 - 662
  • [44] Dominator coloring and CD coloring in almost cluster graphs ☆
    Banik, Aritra
    Kasthurirangan, Prahlad Narasimhan
    Raman, Venkatesh
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2025, 150
  • [45] Coloring Sierpinski graphs and Sierpinski gasket graphs
    Klavzar, Sandi
    [J]. TAIWANESE JOURNAL OF MATHEMATICS, 2008, 12 (02): : 513 - 522
  • [46] Integral distance graphs
    Chen, JJ
    Chang, GJ
    Huang, KC
    [J]. JOURNAL OF GRAPH THEORY, 1997, 25 (04) : 287 - 294
  • [47] Distance dominator packing coloring of type II
    Ferme, Jasmina
    Stesl, Dasa Mesaric
    [J]. QUAESTIONES MATHEMATICAE, 2025, 48 (03) : 437 - 453
  • [48] The relationship between incidence coloring and vertex coloring of graphs
    Wang, Shudong
    Yan, Lijun
    [J]. DYNAMICS OF CONTINUOUS DISCRETE AND IMPULSIVE SYSTEMS-SERIES B-APPLICATIONS & ALGORITHMS, 2007, 14 : 917 - 921
  • [49] On 2-distance 16-coloring of planar graphs with maximum degree at most five
    Deniz, Zakir
    [J]. DISCRETE MATHEMATICS, 2025, 348 (04)
  • [50] Coloring minimal Cayley graphs
    Garcia-Marco, Ignacio
    Knauer, Kolja
    [J]. EUROPEAN JOURNAL OF COMBINATORICS, 2025, 125