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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00338327
Contributor : Daniel Gonçalves <>
Submitted on : Wednesday, November 12, 2008 - 5:02:18 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

242