On star and caterpillar arboricity

doi:10.1016/j.disc.2008.01.041

Discrete Mathematics

Volume 309, Issue 11, 6 June 2009, Pages 3694-3702

https://doi.org/10.1016/j.disc.2008.01.041 Get rights and content

Under an Elsevier user license

open archive

Abstract

We give new bounds on the star arboricity and the caterpillar arboricity of planar graphs with given girth. One of them answers an open problem of Gyárfás and West: there exist planar graphs with track number 4. We also provide new NP-complete problems.

Keywords

NP-completeness

Partitioning problems

Edge coloring