On chromatic Numbers of Close-to-Kneser Distance Graphs

被引：5

作者：

Bobu, A. V. ^{[1
]}

Kupriyanov, A. E. ^{[1
]}

机构：

[1] Lomonosov Moscow State Univ, Fac Math & Mech, Dept Math Stat & Random Proc, Moscow, Russia

来源：

PROBLEMS OF INFORMATION TRANSMISSION | 2016年 / 52卷 / 04期

基金：

俄罗斯基础研究基金会;

关键词：

FORBIDDEN EQUILATERAL TRIANGLE; FINITE SETS; INTERSECTIONS; HYPERGRAPH; THEOREM; EDGES; CONSEQUENCES; SPACE;

D O I：

10.1134/S0032946016040050

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study a family of distance graphs whose structure is close to that of Kneser graphs. We give new lower and upper bounds on the chromatic numbers of such graphs and consider the question of their interrelation. We also describe the structure of some important independence sets for this family of graphs and explicitly compute their cardinalities.

引用

页码：373 / 390

页数：18

共 24 条

[1] The complete nontrivial-intersection theorem for systems of finite sets [J].

Ahlswede, R ;

Khachatrian, LH .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 76 (01) :121-138

[2]

[Anonymous], 2013, Thirty Essays on Geometric Graph Theory, DOI [10.1007/978-1-4614-0110-0_23, DOI 10.1007/978-1-4614-0110-0_23]

[3]

[Anonymous], 1978, The Theory of Error-Correcting Codes

[4] COLORING SOME FINITE SETS IN Rn [J].

Balogh, Jozsef ;

Kostochka, Alexandr ;

Raigorodskii, Andrei .

DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (01) :25-31

[5] Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection [J].

Bobu, A. V. ;

Kupriyanov, A. E. ;

Raigorodskii, A. M. .

SBORNIK MATHEMATICS, 2016, 207 (05) :652-677

[6] On the maximal number of edges in a uniform hypergraph with one forbidden intersection [J].

Bobu, A. V. ;

Kupriyanov, A. E. ;

Raigorodskii, A. M. .

DOKLADY MATHEMATICS, 2015, 92 (01) :401-403

[7] Independence numbers and chromatic numbers of some distance graphs [J].

Bobu, A. V. ;

Kostina, O. A. ;

Kupriyanov, A. E. .

PROBLEMS OF INFORMATION TRANSMISSION, 2015, 51 (02) :165-176

[8]

BRASS P, 2005, RES PROBLEMS DISCRET, DOI DOI 10.1007/0-387-29929-7

[9]

Fikhtengol'ts G.M., 2005, OSNOVY MATEMATICHESK

[10] ALL TRIANGLES ARE RAMSEY [J].

FRANKL, P ;

RODL, V .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1986, 297 (02) :777-779

← 1 2 3 →