On the linear k-arboricity of cubic graphs

✍ Scribed by Bill Jackson; Nicholas C. Wormald

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 231 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00293-6

✦ Synopsis

Bermond et al. [2] conjectured that the edge set of a cubic graph G can be partitioned into two k-linear forests, that is to say two forests whose connected components are paths of length at most k, for all k >/5. We shall prove a weaker result that the statement is valid for all k/> 18.

All graphs considered will be finite. We shall refer to graphs which may contain loops or multiple edges as multigraphs and reserve the term graph for those which do not. A linear forest is a forest each of whose components are paths. The linear arboricity of a graph G, defined by Harary [7], is the minimum number of linear forests required to partition E(G) and is denoted by la(G). It was shown by Akiyama, Exoo and Harary [1] that la(G)=2 when G is cubic. A k-linear forest is a forest consisting of paths of length at most k. The k-linear arboricity of G, introduced by Habib and P6roche [7], is the minimum number of k-linear forests required to partition E(G), and is denoted by lag(G). It is conjectured in [-2] that if G is cubic then las(G) ~< 2. A partial result is obtained by Delamarre et al. [3], who show that lag(G) ~< 2 when k ~> F½] V(G)I-] ~> 4. The purpose of this note is to improve their result, when ] V(G)] /> 36, to:

Theorem. Let G be a cubic graph and k >~ 18 be an integer. Then lak(G) =2.

In order to prove this theorem we shall need the following lemma on matchings in multigraphs.

Lemma. Let H be a multigraph with m edges and maximum degree at most four. Let x be the number of loops in components with only one vertex, and q the number of * Corresponding author.