An intermediate value theorem for the arboricities (Q554848)

Summary: Let \(G\) be a graph. The vertex (edge) arboricity of \(G\), denoted by \(a(G)\) (\(a_1(G)\)), is the minimum number of subsets into which the vertex (edge) set of \(G\) can be partitioned so that each subset induces an acyclic subgraph. Let \(d\) be a graphical sequence and let \({\mathcal{R}}(d)\) be the class of realizations of \(d\). We prove that if \(\pi \in \{a,a_1\}\), then there exist integers \(x(\pi)\) and \(y(\pi)\) such that \(d\) has a realization \(G\) with \(\pi(G) = z\) if and only if \(z\) is an integer satisfying \(\pi(z) \leq z \leq y(z)\). Thus, for an arbitrary graphical sequence \(d\) and \(\pi \in \{a,a_1\}\), the two invariants \(x(\pi) = \min(\pi,d) := \min\{\pi(G) : G \in \mathcal{R}(d)\}\) and \(y(\pi) \max(\pi,d) := \max\{\pi(G) : G \in \mathcal{R}(d)\}\) naturally arise and hence \(\pi(d) := \{\pi(G) : G \in \mathcal{R}(d)\} = \{z \in \mathbb{Z} : x(\pi) \leq z \leq y(\pi)\}\). We write \(d = r^n := (r,r,\dots,,r)\) for the degree sequence of an \(r\)-regular graph of order \(n\). We prove that \(a_1(r^n) = \{\lceil(r+1)/2\rceil\}\). We consider the corresponding extremal problem on vertex arboricity and obtain \(\min(a,r^n)\) in all situations and \(\max(a,r^n)\) for all \(n \geq 2r + 2\) .