Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).

# Linear choosability of graphs

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [6 references]

https://hal.inria.fr/hal-01184391
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 11:39:17 AM
Last modification on : Saturday, June 25, 2022 - 10:35:51 AM
Long-term archiving on: : Sunday, November 15, 2015 - 11:06:19 AM

### File

dmAE0120.pdf
Publisher files allowed on an open archive

### Citation

Louis Esperet, Mickael Montassier, André Raspaud. Linear choosability of graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.99-104, ⟨10.46298/dmtcs.3434⟩. ⟨hal-01184391⟩

Record views