It is well-known that approximating the chromatic number within a factor of
cannot be done in polynomial time for any
> 0, unless
. Also, it is known that computing the list-chromatic number is much harder than the chromatic number (assuming that the complexity classes
are different). In fact, the problem of deciding if a given graph is
-list-colorable for a function
≥ 3 is
In this paper, we are concerned with the following questions:
Given a graph embedded on a surface of bounded genus, what is its list-chromatic number ?
Given a graph embedded on a surface of bounded genus with list-chromatic number
, what is the least
) such that the graph can be efficiently and legally colored given a list (coloring scheme) of order
The seminal result of Thomassen  gives rise to answers for these problems when a given graph is planar. In fact, he gave a polynomial time algorithm to 5-list-color a planar graph. Thomassen’s result together with the hardness result (distinguishing between 3, 4 and 5 list-colorability is NP-complete for planar graphs and bounded genus graphs) gives an additive approximation algorithm for list-coloring planar graphs within 2 of the list-chromatic number.
Our main result is to extend this result to bounded genus graphs. In fact, our algorithm gives a list-coloring when each vertex has a list with at least
) + 2 colors available. The time complexity is
It also generalizes the other deep result of Thomassen  who gave an additive approximation algorithm for graph-coloring bounded genus graphs within 2 of the chromatic number.
This theorem can be compared to the result by Kawarabayashi and Mohar(STOC’06) who gave an
)-approximation algorithm for list-coloring graphs with no
-minors. For minor-closed graphs, there is a 2-approximation algorithm for graph-coloring by Demaine, Hajiaghayi and Kawarabayashi (FOCS’05), but it seems that there is a huge gap between list-coloring and graph-coloring in minor-closed family of graphs. On the other hand, this is not the case for bounded genus graphs, as we pointed out above.