Vertex arboricity and maximum degree (Q1894756): Difference between revisions

This paper mainly proves that if a connected graph \(G= (V,E)\) is neither a cycle nor a clique, then there is a coloring of \(V\) with at most \(\lceil {{\Delta (G)} \over 2} \rceil\) colors such that all color classes induce forests and one of them is a minimum induced forest in \(G\).