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 条
  • [31] On the Comparison of the Distinguishing Coloring and the Locating Coloring of Graphs
    M. Korivand
    A. Erfanian
    Edy Tri Baskoro
    Mediterranean Journal of Mathematics, 2023, 20
  • [32] Indicated coloring of graphs
    Grzesik, Andrzej
    DISCRETE MATHEMATICS, 2012, 312 (23) : 3467 - 3472
  • [33] On the Comparison of the Distinguishing Coloring and the Locating Coloring of Graphs
    Korivand, M.
    Erfanian, A.
    Baskoro, Edy Tri
    MEDITERRANEAN JOURNAL OF MATHEMATICS, 2023, 20 (05)
  • [34] Circular coloring and fractional coloring in planar graphs
    Hu, Xiaolan
    Li, Jiaao
    JOURNAL OF GRAPH THEORY, 2022, 99 (02) : 312 - 343
  • [35] COLORING OF BIFUZZY GRAPHS
    Shahzadi, Sundas
    Akram, Muhammad
    ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2016, (36): : 429 - 444
  • [36] Colinear Coloring on Graphs
    Ioannidou, Kyriaki
    Nikolopoulos, Stavros D.
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2009, 5431 : 117 - 128
  • [37] Coloring of character graphs
    Ebrahimi, Mahdi
    Iranmanesh, Ali
    COMMUNICATIONS IN ALGEBRA, 2017, 45 (01) : 227 - 233
  • [38] On coloring box graphs
    Hogan, Emilie
    O'Rourke, Joseph
    Traub, Cindy
    Veomett, Ellen
    DISCRETE MATHEMATICS, 2015, 338 (02) : 209 - 216
  • [39] Coloring Artemis graphs
    Leveque, Benjamin
    Maffray, Frederic
    Reed, Bruce
    Trotignon, Nicolas
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (21-23) : 2234 - 2240
  • [40] On the dynamic coloring of graphs
    Alishahi, Meysam
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (2-3) : 152 - 156