On Star and Caterpillar Arboricity

Daniel Gonçalves; Pascal Ochem

doi:10.1016/j.disc.2008.01.041

Back

Journal article

Open access

Peer reviewed

On Star and Caterpillar Arboricity

Daniel Gonçalves and Pascal Ochem

Discrete Mathematics, Vol.309(11), pp.3694-3702

2009

DOI: https://doi.org/10.1016/j.disc.2008.01.041

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.

Files and links (2)

url

Find in HALView

url

https://doi.org/10.1016/j.disc.2008.01.041View

Published (Version of record) Open

Metrics

1 Record Views

Details

Title: On Star and Caterpillar Arboricity
Creators - without role: Daniel Gonçalves - Centre National de la Recherche Scientifique
Pascal Ochem - Université Paris-Sud
Publication Details: Discrete Mathematics, Vol.309(11), pp.3694-3702
Identifiers: 9942143309311
Academic Unit: Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
Language: English
Resource Type: Journal article
Local Fields: lirmm-00338327