DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Linear choosability of graphs

Louis Esperet, Mickaël Montassier, André Raspaud


A proper vertex coloring of a non oriented graph G=(V,E) is linear if the graph induced by the vertices of two color classes is a forest of paths. A graph G is L-list colorable if for a given list assignment L={L(v): v∈V}, there exists a proper coloring c of G such that c(v)∈L(v) for all v∈V. If G is L-list colorable for every list assignment with |L(v)|≥k for all v∈V, then G is said k-choosable. A graph is said to be lineary k-choosable if the coloring obtained is linear. In this paper, we investigate the linear choosability of graphs for some families of graphs: graphs with small maximum degree, with given maximum average degree, planar graphs... Moreover, we prove that determining whether a bipartite subcubic planar graph is lineary 3-colorable is an NP-complete problem.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional