On Star and Caterpillar Arboricity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Mathematics Année : 2009

On Star and Caterpillar Arboricity

Daniel Gonçalves
Algorithmes, Graphes et Combinatoire
CV
Pascal Ochem
Laboratoire de Recherche en Informatique
CV

Résumé

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.

Domaines

Combinatoire [math.CO]

Daniel Gonçalves  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00338327

Soumis le : mercredi 12 novembre 2008-17:02:18

Dernière modification le : lundi 22 avril 2024-10:05:14

Consulter le texte intégral

Dates et versions

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

Identifiants

Citer

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⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

EC-PARIS CNRS UMR8623 ALGCO LIRMM UNIV-PARIS-SACLAY MIPS UNIV-MONTPELLIER
170 Consultations
0 Téléchargements

Altmetric

Partager

More