The complexity of planar graph choosability

Simple item page
dc.creatorGutner, Shai
dc.date2008-02-19
dc.date.accessioned2026-07-07T09:21:45Z
dc.date.available2026-07-07T09:21:45Z
dc.descriptionA graph $G$ is {\em $k$-choosable} if for every assignment of a set $S(v)$ of $k$ colors to every vertex $v$ of $G$, there is a proper coloring of $G$ that assigns to each vertex $v$ a color from $S(v)$. We consider the complexity of deciding whether a given graph is $k$-choosable for some constant $k$. In particular, it is shown that deciding whether a given planar graph is 4-choosable is NP-hard, and so is the problem of deciding whether a given planar triangle-free graph is 3-choosable. We also obtain simple constructions of a planar graph which is not 4-choosable and a planar triangle-free graph which is not 3-choosable.
dc.identifierhttps://arxiv.org/abs/0802.2668
dc.identifierhttp://arxiv.org/abs/0802.2668
dc.identifierDiscrete Math. 159 (1996), 119-130
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155136
dc.subjectDiscrete Mathematics
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.titleThe complexity of planar graph choosability
dc.typetext

Files

Collections

arXiv