Edge arboricity : Do we need equitabilility ?

Abstract

In this paper we study a new variant of graph arboricity, which requires all the forests to have the same number of edges (up to a difference of 1). We prove that the new variant, which we call equitable arboricity, is equivalent to ordinary arboricity. In other words we show that any arborescent decomposition of a graph can be transformed into an equitable one without modifying the number of used forests.

arXiv commentA colleague just informed me that the result is an obvious consequence of the exchange axiom in matroïds