An Intermediate Value Theorem for the Arboricities

الملخص EN

Let G be a graph.

The vertex (edge) arboricity of G denoted by a(G) (a1(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):=max{π(G):G∈R(d)} naturally arise and hence π(d):={π(G):G∈R(d)}={z∈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 min(a,rn) in all situations and max(a,rn) for all n≥2r+2.