# P and NPC results on Genus-g graphs being c-Colorable

## A lot of this work depends on list coloring.

## Here is the Graph List Coloring problem: Given a graph G and, for each

## vertex v a list of colors L(v), can you color G where v is colored with

## some vertex in L(v). A graph is k-choosable if it is list-colorable where

## each L(v) is a subset of {1,…,k}

## If we are going to look at graphs of genus g we need to find the genus of a graph. Hence we need this paper:

## Papers on 5-colorability