On Star and Caterpillar Arboricity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Discrete Mathematics Year : 2009

On Star and Caterpillar Arboricity

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

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.

Domains

Combinatorics [math.CO]

Daniel Gonçalves  : Connect in order to contact the contributor

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

Submitted on : Wednesday, November 12, 2008-5:02:18 PM

Last modification on : Monday, April 22, 2024-10:05:14 AM

Consult the full text

Dates and versions

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

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

EC-PARIS CNRS UMR8623 ALGCO LIRMM UNIV-PARIS-SACLAY MIPS UNIV-MONTPELLIER
155 View
0 Download

Altmetric

Share

More