On Star and Caterpillar Arboricity

Daniel Gonçalves; Pascal Ochem

doi:10.1016/j.disc.2008.01.041

Article Dans Une Revue Discrete Mathematics Année : 2009

On Star and Caterpillar Arboricity

(1) , (2)

1
2

Daniel Gonçalves

Fonction : Auteur
PersonId : 7100
IdHAL : daniel-goncalves
ORCID : 0000-0003-3228-9622
IdRef : 117629413

Algorithmes, Graphes et Combinatoire

Pascal Ochem

Fonction : Auteur
PersonId : 7098
IdHAL : pascal-ochem
ORCID : 0000-0001-5504-4586
IdRef : 109150902

Laboratoire de Recherche en Informatique

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

Dates et versions

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

Identifiants

HAL Id : lirmm-00338327 , version 1
DOI : 10.1016/j.disc.2008.01.041

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

151 Consultations

0 Téléchargements

On Star and Caterpillar Arboricity

Résumé

Domaines

Dates et versions

Identifiants

Citer

Exporter

Collections

Altmetric

Partager