## Louis Esperet ; Mickael Montassier ; André Raspaud - Linear choosability of graphs

dmtcs:3434 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3434
Linear choosability of graphs

Authors: Louis Esperet 1; Mickael Montassier 1; André Raspaud 1

• 1 Laboratoire Bordelais de Recherche en Informatique

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.

Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: vertex-coloring,list,acyclic,3-frugal,choosability under constraints.,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

## Linked publications - datasets - softwares

 Source : ScholeXplorer IsRelatedTo DOI 10.1007/s00373-010-1009-7 10.1007/s00373-010-1009-7 10.1007/s00373-010-1009-7 Linear and 2-Frugal Choosability of Graphs of Small Maximum Average Degree