A Short Proof of the Linear Arboricity for Cubic Graphs

概要

論文の詳細を見る
Akiyama, Exoo and Harary proved in [1] that the linear arboricity for cubic graphs is 2. They did not seek a short proof of this result but derived it in order to illustrate certain proof techniques, so called "necessary subgraphs for cubic graphs." The purpose of this note is to present a short proof for this result by applying Vizing's Theorem on the edge chromatic number. In a linear forest, each component is a path. The linear arboricity (or path chromatic index) Ξ(G) of a graph G is defined by Harary in [3] as the minimum number of linear forests whose union is G. Note that the Greek letter, capital Xi, looks like three paths! An assignment of colors to the edges of a nonempty graph G so that adjacent edges are colored differently is an edge coloring of G (an n-edge coloring if n colors are used). The graph G is n-edge colorable if there exists an m-edge coloring of G for some m≦n. The minimum n for which a graph G is n-edge colorable is its edge chromatic number (or chromatic index) and is denoted by x'(G).
日本医科大学の論文
1982-02-27