Skip to Main content Skip to Navigation
Journal articles

On Star and Caterpillar Arboricity

Daniel Gonçalves 1 Pascal Ochem 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Daniel Gonçalves <>
Submitted on : Wednesday, November 12, 2008 - 5:02:18 PM
Last modification on : Wednesday, November 4, 2020 - 6:08:03 PM

Links full text




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



Record views