Perhaps a proof theorist can give a truly horrific bound? Charles Greathouse

--It sounds like what you are asking for, is this question: Is there a function F(N), such that every N-chromatic graph, contains an N-chromatic subgraph with at most F(N) vertices? I believe the answer is "no." In particular F(3) does not exist because any odd-cycle is 3-chromatic but no subgraph is.