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 Connect in order to contact the contributor
Submitted on : Wednesday, November 12, 2008 - 5:02:18 PM
Last modification on : Thursday, July 8, 2021 - 3:48:24 AM

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