Copyright © 2011 Avapa Chantasartrassmee and Narong Punnim. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Let be a graph. The vertex (edge) arboricity of denoted by is the minimum number of subsets into which the vertex (edge) set of can be partitioned so that each subset induces an acyclic subgraph. Let be a graphical sequence and let be the class of realizations of . We prove that if , then there exist integers and such that has a realization with if and only if is an integer satisfying . Thus, for an arbitrary graphical sequence and , the two invariants and   naturally arise and hence We write for the degree sequence of an -regular graph of order . We prove that . We consider the corresponding extremal problem on vertex arboricity and obtain in all situations and for all .