Independence numbers and chromatic numbers of some distance graphs

被引：0
|
作者：
A. V. Bobu
O. A. Kostina
A. E. Kupriyanov
机构：
[1] Lomonosov Moscow State University,Department of Mathematical Statistics and Random Processes, Faculty of Mathematics and Mechanics
来源：
Problems of Information Transmission | 2015年 / 51卷
关键词：
Information Transmission; Chromatic Number; Prime Power; Distance Graph; Intersection Theorem;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study a family of distance graphs in ℝn. We present bounds for independence numbers which are asymptotically tight as n → ∞. We substantially improve upper bounds on chromatic numbers of these graphs, and in a number of cases we give explicit constructions of independence sets.
引用
收藏
页码：165 / 176
页数：11
相关论文
共 50 条
  • [1] Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
    Bogolubsky, L. I.
    Gusev, A. S.
    Pyaderkin, M. M.
    Raigorodskii, A. M.
    SBORNIK MATHEMATICS, 2015, 206 (10) : 1340 - 1374
  • [2] Chromatic Numbers of Some Distance Graphs
    Zakharov, D. A.
    MATHEMATICAL NOTES, 2020, 107 (1-2) : 238 - 246
  • [3] Chromatic Numbers of Some Distance Graphs
    D. A. Zakharov
    Mathematical Notes, 2020, 107 : 238 - 246
  • [4] Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
    Bogolyubskii, L. I.
    Gusev, A. S.
    Pyaderkin, M. M.
    Raigorodskii, A. M.
    DOKLADY MATHEMATICS, 2014, 90 (01) : 462 - 465
  • [5] Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs
    L. I. Bogolyubskii
    A. S. Gusev
    M. M. Pyaderkin
    A. M. Raigorodskii
    Doklady Mathematics, 2014, 90 : 462 - 465
  • [6] Circular chromatic numbers of some distance graphs
    Lin, WS
    Lam, PCB
    Song, ZM
    DISCRETE MATHEMATICS, 2005, 292 (1-3) : 119 - 130
  • [7] Distance graphs with large chromatic numbers and small clique numbers
    A. B. Kupavskii
    A. M. Raigorodskii
    Doklady Mathematics, 2012, 85 : 394 - 398
  • [8] On the structure of distance graphs with large chromatic numbers
    A. M. Raigorodskii
    Mathematical Notes, 2006, 80 : 451 - 453
  • [9] On the structure of distance graphs with large chromatic numbers
    Raigorodskii, A. M.
    MATHEMATICAL NOTES, 2006, 80 (3-4) : 451 - 453
  • [10] Chromatic numbers of exact distance graphs
    van den Heuvel, Jan
    Kierstead, H. A.
    Quiroz, Daniel A.
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2019, 134 : 143 - 163
12345