On Star and Caterpillar Arboricity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2009

On Star and Caterpillar Arboricity

Pascal Ochem

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.

Dates and versions

lirmm-00338327 , version 1 (12-11-2008)

Identifiers

Cite

Daniel Gonçalves, Pascal Ochem. On Star and Caterpillar Arboricity. Discrete Mathematics, 2009, 309 (11), pp.3694-3702. ⟨10.1016/j.disc.2008.01.041⟩. ⟨lirmm-00338327⟩
155 View
0 Download

Altmetric

Share

More