Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for all vertices of the given graph.
The complexity class poly-APX contains all NP optimization problems that can be approximated within a factor that is polynomial in the size of the input. The notion of C-reducibility concerns approximation preserving reductions, which keep the performance ratio of the feasible solutions under consideration within a linear factor. For definitions regarding approximation preserving reducibilities, see P. Crescenzi: A short guide to approximation preserving reducibilites, CCC '97.
EDIT (1.8.2014): Somewhat related, I've found in the paper "on syntactic versus computational views of approximability" by Khanna, Motwani, Sudan and Vazirani (SICOMP 28(1):164-191) a remark stating that GRAPH COLORING and MAX CLIQUE are both in poly-APX-PB and interreducible (Remark 6 in that paper). I understand this is meant with respect to E-reducibility defined in that paper. Later, in the sketch of proof of Theorem 6 in that paper, I understand that they imply that MAX CLIQUE is complete for poly-APX-PB under E-reductions. I would also be grateful for a proof that GRAPH COLORING is complete for poly-APX-PB w.r.t. E-reducibility.