On the connection between the chromatic number of a~graph and the number of cycles, covering a~vertex or an edge
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 5-13
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{ZNSL_2016_450_a0,
author = {S. L. Berlov and K. I. Tyschuk},
title = {On the connection between the chromatic number of a~graph and the number of cycles, covering a~vertex or an edge},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {5--13},
publisher = {mathdoc},
volume = {450},
year = {2016},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/}
}
TY - JOUR AU - S. L. Berlov AU - K. I. Tyschuk TI - On the connection between the chromatic number of a~graph and the number of cycles, covering a~vertex or an edge JO - Zapiski Nauchnykh Seminarov POMI PY - 2016 SP - 5 EP - 13 VL - 450 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/ LA - ru ID - ZNSL_2016_450_a0 ER -
%0 Journal Article %A S. L. Berlov %A K. I. Tyschuk %T On the connection between the chromatic number of a~graph and the number of cycles, covering a~vertex or an edge %J Zapiski Nauchnykh Seminarov POMI %D 2016 %P 5-13 %V 450 %I mathdoc %U http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/ %G ru %F ZNSL_2016_450_a0
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. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VIII, Tome 450 (2016), pp. 5-13. http://geodesic.mathdoc.fr/item/ZNSL_2016_450_a0/