  Robin Thomas asked whether for every proper minor-closed class C, there
exists a polynomial-time algorithm approximating the chromatic number of graphs
from C up to a constant additive error independent on the class C. We show this
is not the case: unless P=NP, for every integer k>=1, there is no
polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using at most
chi(G)+k-1 colors. More generally, for every k>=1 and 1<=\beta<=4/3, there is
no polynomial-time algorithm to color a K_{4k+1}-minor-free graph G using less
than beta.chi(G)+(4-3beta)k colors. As far as we know, this is the first
non-trivial non-approximability result regarding the chromatic number in proper
minor-closed classes.
  We also give somewhat weaker non-approximability bound for
K_{4k+1}-minor-free graphs with no cliques of size 4. On the positive side, we
present additive approximation algorithm whose error depends on the apex number
of the forbidden minor, and an algorithm with additive error 6 under the
additional assumption that the graph has no 4-cycles.
