LAUSR

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 ek!2−k+12$$ \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.