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).
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

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

Identifiers

Collections

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⟩

Share

Metrics

Record views

51

Files downloads

440