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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 309 (11), pp.3694-3702. 〈10.1016/j.disc.2008.01.041〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00338327
Contributeur : Daniel Gonçalves <>
Soumis le : mercredi 12 novembre 2008 - 17:02:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

193