An intermediate value theorem for the arboricities

Abstract

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 R (d) be the class of realizations of d. We prove that if π∈{a, a1}, then there exist integers x (π) and y (π) such that d has a realization G with π(G) = z if and only if z is an integer satisfying x (π) < z < y (π). Thus, for an arbitrary graphical sequence d and π∈{a, a1}, the two invariants x (π) = min (π, d): = min { (G): G R (d) } and y (π) = max (π, d): = m a x {π G): G ∈ R (d) } naturally arise and hence (d): = {π(G): G ∈ R (d) } = { z ∈ ℤ: x (π)< z < y (π)}. We write d = rn: = (r, r, ⋯, r) for the degree sequence of an r -regular graph of order n. We prove that a1 (rn) = {(r + 1) / 2 }. We consider the corresponding extremal problem on vertex arboricity and obtain m in (a, rn) in all situations and max (a, rn) for all n > 2 r + 2. © 2011 Avapa Chantasartrassmee and Narong Punnim.