|
Zapiski Nauchnykh Seminarov POMI, 2016, Volume 450, Pages 5–13
(Mi znsl6333)
|
|
|
|
On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge
S. L. Berlov, K. I. Tyschuk Physical and Mathematical Lyceum 239, St. Petersburg, Russia
Abstract:
We prove several tight bounds on the chromatic number of a graph in terms of the minimal number of simple cycles, covering a vertex or an edge of this graph. Namely, we prove that $\chi(G)\leq 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 $[\frac{ek!}2-\frac{k+1}2]$ simple cycles. Tight bounds on the number of simple cycles covering an edge or a vertex of a $k$-critical graph are also proved.
Key words and phrases:
proper coloring, chromatic number.
Received: 11.10.2016
Citation:
S. L. Berlov, K. I. Tyschuk, “On the connection between the chromatic number of a graph and the number of cycles, covering a vertex or an edge”, Combinatorics and graph theory. Part VIII, Zap. Nauchn. Sem. POMI, 450, POMI, St. Petersburg, 2016, 5–13; J. Math. Sci. (N. Y.), 232:1 (2018), 1–5
Linking options:
https://www.mathnet.ru/eng/znsl6333 https://www.mathnet.ru/eng/znsl/v450/p5
|
Statistics & downloads: |
Abstract page: | 165 | Full-text PDF : | 73 | References: | 29 |
|