Name
Abstract | ||
|---|---|---|
The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1984, Akiyama et al. (1) stated the Linear Arboricity Conjecture (LAC), that the linear arboricity of any simple graph of maximum degree is either 2 or +1 2 . In (14, 17) it was proven that LAC holds for all planar graphs. LAC implies that for odd, la( G) = 2 . We conjecture that for planar graphs this equality is true also for any even 6. In this paper we show that it is true for any even 10, leaving open only the cases = 6 ; 8. We present also anO(n logn) algorithm for partitioning a planar graph into maxfla(G); 5g linear forests, which is optimal when 9. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-13073-1_19 | Journal of Graph Theory |
Keywords | DocType | Volume |
maximum degree,planar linear arboricity conjecture,linear arboricity conjecture,linear forest,planar graph,connected component,simple graph,graph g,linear arboricity,minimum number,graph theory | Journal | 69 |
Issue | ISSN | ISBN |
4 | 10970118 | 3-642-13072-0 |
Citations | PageRank | References |
2 | 0.39 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marek Cygan | 1 | 556 | 40.52 |
| Łukasz Kowalik | 2 | 258 | 22.43 |
| Borut Luzar | 3 | 42 | 10.86 |