Linear arboricity of degenerate graphs

Abstract: A linear forest is a union of vertex-disjoint paths, and the linear arboricity of a graph

G

, denoted by

o p e r a t o r n a m e l a (G)

, is the minimum number of linear forests needed to partition the edge set of

G

. Clearly,

o p e r a t o r n a m e l a (G) g e l c e i l D e l t a (G) / 2 c e i l

for a graph

G

with maximum degree

D e l t a (G)

. On the other hand, the Linear Arboricity Conjecture due to Akiyama, Exoo, and Harary from 1981 asserts that

o p e r a t o r n a m e l a (G) l e q l c e i l (D e l t a (G) + 1) / 2 c e i l

for every graph

G

. This conjecture has been verified for planar graphs and graphs whose maximum degree is at most

6

, or is equal to

8

or

10

. Given a positive integer

k

, a graph

G

is

k

-degenerate if it can be reduced to a trivial graph by successive removal of vertices with degree at most

k

. We prove that for any

k

-degenerate graph

G

,

o p e r a t o r n a m e l a (G) = l c e i l D e l t a (G) / 2 c e i l

provided

D e l t a (G) g e 2 k^{2} - k

.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Linear arboricity of degenerate graphs