Linear choosability of graphs |
| |
Authors: | Louis Esperet André Raspaud |
| |
Institution: | LaBRI UMR CNRS 5800, Université Bordeaux I, 33405 Talence Cedex, France |
| |
Abstract: | A proper vertex coloring of a non-oriented graph G is linear if the graph induced by the vertices of any two color classes is a forest of paths. A graph G is linearly L-list colorable if for a given list assignment L={L(v):v∈V(G)}, there exists a linear coloring c of G such that c(v)∈L(v) for all v∈V(G). If G is linearly L-list colorable for any list assignment with |L(v)|?k for all v∈V(G), then G is said to be linearly k-choosable. In this paper, we investigate the linear choosability for some families of graphs: graphs with small maximum degree, with given maximum average degree, outerplanar and planar graphs. Moreover, we prove that deciding whether a bipartite subcubic planar graph is linearly 3-colorable is an NP-complete problem. |
| |
Keywords: | Graph coloring Choosability under constraints |
本文献已被 ScienceDirect 等数据库收录! |
|