Independent Sets and Chromatic Numbers of Circle Graphs

被引：0
作者：
Berlov S.L. [1 ]
机构：
[1] Yaroslavl’ State University, Yaroslavl’
来源：
Journal of Mathematical Sciences | 2015年 / 204卷 / 2期
关键词：
Positive Integer; Chromatic Number; Induction Step; Arbitrary Order; Maximum Clique;
D O I：
10.1007/s10958-014-2196-1
中图分类号：
学科分类号：
摘要：
Let the vertices of a circle graph be divided into several groups. This paper contains lower bounds on the size of an independent set that can be contained in one group of this subdivision. Bibliography: 7 titles. © 2014, Springer Science+Business Media New York.
引用
收藏
页码：181 / 184
页数：3
相关论文
共 50 条
[41]   Improved upper bound for the degenerate and star chromatic numbers of graphs [J].
Cai, Jiansheng ;
Li, Xueliang ;
Yan, Guiying .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 34 (02) :441-452
[42]   Resource placement in networks using chromatic sets of power graphs [J].
Imani, Navid ;
Sarbazi-Azad, Hamid ;
Akl, Selim G. .
COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2007, 4649 :158-+
[43]   Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers [J].
Kupavskii, A. B. .
IZVESTIYA MATHEMATICS, 2014, 78 (01) :59-89
[44]   Maximum independent sets on random regular graphs [J].
Ding, Jian ;
Sly, Allan ;
Sun, Nike .
ACTA MATHEMATICA, 2016, 217 (02) :263-340
[45]   Fair splittings by independent sets in sparse graphs [J].
Black, Alexander ;
Cetin, Umur ;
Frick, Florian ;
Pacun, Alexander ;
Setiabrata, Linus .
ISRAEL JOURNAL OF MATHEMATICS, 2020, 236 (02) :603-627
[46]   Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra [J].
Rubanov, O. I. .
MATHEMATICAL NOTES, 2007, 82 (5-6) :718-721
[47]   Ball packings with high chromatic numbers from strongly regular graphs [J].
Chen, Hao .
DISCRETE MATHEMATICS, 2017, 340 (07) :1645-1648
[48]   Chromatic numbers of 3-dimensional distance graphs containing no tetrahedra [J].
O. I. Rubanov .
Mathematical Notes, 2007, 82 :718-721
[49]   Chromatic sets of power graphs and their application to resource placement in multicomputer networks [J].
Imani, N. ;
Sarbazi-Azad, H. ;
Akl, S. G. ;
Moinzadeh, P. .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2009, 58 (03) :403-413
[50]   Circular chromatic number of distance graphs with distance sets of cardinality 3 [J].
Zhu, XD .
JOURNAL OF GRAPH THEORY, 2002, 41 (03) :195-207
12345