Vol 232, No 1 (2018)

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.

A vertex coloring of a graph is called dynamic if the neighborhood of any vertex of degree at least 2 contains at least two vertices of distinct colors. Similarly to the chromatic number χ(G) of a graph G, one can define its dynamic number χ_d(G) (the minimum number of colors in a dynamic coloring) and dynamic chromatic number χ₂(G) (the minimum number of colors in a proper dynamic coloring). We prove that χ₂(G) ≤ χ(G) · χ_d(G) and construct an infinite series of graphs for which this bound on χ₂(G) is tight.

For a graph G, set \( k=\left\lceil \frac{2\Delta (G)}{\delta (G)}\right\rceil \) We prove that χ₂(G) ≤ (k+1)c. Moreover, in the case where k ≥ 3 and Δ(G) ≥ 3, we prove the stronger bound χ₂(G) ≤ kc.

Let G be a connected graph on n ≥ 2 vertices with girth at least g such that the length of a maximal chain of successively adjacent vertices of degree 2 in G does not exceed k ≥ 1. Denote by u(G) the maximum number of leaves in a spanning tree of G. We prove that u(G) ≥ α_g,k(υ(G) − k − 2) + 2 where \( {\alpha}_{g,1}=\frac{\left[\frac{g+1}{2}\right]}{4\left[\frac{g+1}{2}\right]+1} \) and \( {\alpha}_{g,k}=\frac{1}{2k+2} \) for k ≥ 2. We present an infinite series of examples showing that all these bounds are tight.

A graph is called cyclically 4-edge-connected if removing any three edges from it results in a graph in which at most one connected component contains a cycle. A 3-connected graph is 4-edge-connected if and only if removing any three edges from it results in either a connected graph or a graph with exactly two connected components one of which is a single-vertex one. We show how to associate with any 3-connected graph a tree of components such that every component is a 3-connected and cyclically 4-edge-connected graph.