The complexity of planar graph choosability

Details The complexity of planar graph choosability The complexity of planar graph choosability

2008-02-19

arxiv.org/abs/0802.2668v1

Discrete Math. 159 (1996), 119-130

Computer Science

Discrete Mathematics

Scientific paper

A 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.

Affiliated with

Also associated with

No associations

Rating

The complexity of planar graph choosability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The complexity of planar graph choosability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of planar graph choosability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-338809