On the Connection Between the Chromatic Number of a Graph and the Number of Cycles Covering a Vertex or an Edge
- 作者: Berlov S.1, Tyschuk K.1
-
隶属关系:
- Physics and Mathematics Lyceum 239
- 期: 卷 232, 编号 1 (2018)
- 页面: 1-5
- 栏目: Article
- URL: https://journals.rcsi.science/1072-3374/article/view/241246
- DOI: https://doi.org/10.1007/s10958-018-3853-6
- ID: 241246
如何引用文章
详细
We prove several tight bounds on the chromatic number of a graph in terms of the minimum number of simple cycles covering a vertex or an edge of this graph. Namely, we prove that X(G) ≤ k in the following two cases: any edge of G is covered by less than [e(k − 1) ! − 1] simple cycles, or any vertex of G is covered by less than \( \left[\frac{ek!}{2}-\frac{k+1}{2}\right] \) simple cycles. Tight bounds on the number of simple cycles covering an edge or a vertex of a k-critical graph are also proved.
作者简介
S. Berlov
Physics and Mathematics Lyceum 239
编辑信件的主要联系方式.
Email: sberlov@rambler.ru
俄罗斯联邦, St.Petersburg
K. Tyschuk
Physics and Mathematics Lyceum 239
Email: sberlov@rambler.ru
俄罗斯联邦, St.Petersburg