The linear k-arboricity of the Mycielski graph M(K_n)

摘要

A linear k-forest of an undirected graph G is a subgraph of G whose components are paths with lengths at most k. The linear k-arboricity Of G, denoted by la_k(G), is the minimum number of linear k-forests needed to partition the edge set E(G) of G. In case that the lengths of paths are not restricted, we then have the linear arboricity of G, denoted by la(G). In this paper, the exact values of the linear 3-arboricity and the linear arboricity of the Mycielski graph M(K_n), and the linear k-arboricity of the Mycielski graph M(K_n) when n is even and k ≥ 5, are obtained.