The list linear arboricity of planar graphs

Xinhui An, and Baoyindureng Wu. "The list linear arboricity of planar graphs." Discussiones Mathematicae Graph Theory 29.3 (2009): 499-510. <http://eudml.org/doc/271000>.

@article{XinhuiAn2009,
abstract = {The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ \{3,4,5\}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9.},
author = {Xinhui An, Baoyindureng Wu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list coloring; linear arboricity; list linear arboricity; planar graph},
language = {eng},
number = {3},
pages = {499-510},
title = {The list linear arboricity of planar graphs},
url = {http://eudml.org/doc/271000},
volume = {29},
year = {2009},
}

TY - JOUR
AU - Xinhui An
AU - Baoyindureng Wu
TI - The list linear arboricity of planar graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2009
VL - 29
IS - 3
SP - 499
EP - 510
AB - The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. An and Wu introduce the notion of list linear arboricity lla(G) of a graph G and conjecture that lla(G) = la(G) for any graph G. We confirm that this conjecture is true for any planar graph having Δ ≥ 13, or for any planar graph with Δ ≥ 7 and without i-cycles for some i ∈ {3,4,5}. We also prove that ⌈½Δ(G)⌉ ≤ lla(G) ≤ ⌈½(Δ(G)+1)⌉ for any planar graph having Δ ≥ 9.
LA - eng
KW - list coloring; linear arboricity; list linear arboricity; planar graph
UR - http://eudml.org/doc/271000
ER -