Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648595 | Discrete Mathematics | 2009 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Gonçalves, Pascal Ochem,