|
|||||
|
|
On star and caterpillar arboricity |
|
| Authors: | Daniel Gonç alves,Pascal Ochem |
| Affiliation: | a LIRMM UMR 5506, CNRS, Université Montpelier 2, 161 rue Ada, 34392 Montpellier Cedex 5, France b LRI UMR 8623, CNRS, Université Paris-Sud, Bât 490, 91405 Orsay Cedex, France |
| 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. |
| Keywords: | NP-completeness Partitioning problems Edge coloring |
| 本文献已被 ScienceDirect 等数据库收录！ | |