Likely I am misunderstanding/missing something, but a claim in a paper appears wrong to me.

According to Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation p. 2

Unless $NP=ZPP$, there is no polynomial-time algorithm to approximate $\chi'(L^k(G))$ to within a factor of $n^{1/3-\epsilon}$ for $k \in \{2,3\}$ and $n^{1/2-\epsilon}$ for $k \ge 4$.

$\chi'$ is the chromatic index and $L^k(G)$ is the $k$-th power of the line graph.

Let $\Delta$ be the maximum degree of $\chi'(L^k(G))$. It is easy to compute. The chromatic index is either $\Delta$ or $\Delta+1$. Choosing the latter for the approximation gives absolute error of at most $1$, which is the best absolute error for integers (not counting equality).

This appears to contradict hardness of approximation, since it is the best possible approximation, not counting exact result.

Q1 What is wrong with this seeming contradiction?


1 Answer 1


I think you are correct. The chromatic index is easy to "approximate".

I believe that the authors meant $\chi(L^k(G))$ instead of $\chi'({L}^k(G))$. Notice that in the Theorem 1 on p2, it is mentioned that the result you state implies the hardness of the strong edge coloring.

On p5, it is told that the strong chromatic index $\chi'_S(G)$ is equal to $\chi(L^2(G))$. Thus the case $k = 2$ is probably what the authors were talking about in Theorem 1, which makes more sense with $\chi(L^k(G))$ instead of $\chi'({L}^k(G))$.

  • $\begingroup$ Thank you. Indeed they define strong edge coloring in a very weird way, which becomes the usual one after dropping the prime. $\endgroup$
    – joro
    Commented Jul 8, 2015 at 6:28
  • $\begingroup$ The square of line graph need not be line graph, which doesn't make sense in edge coloring. Should the correct statement be $\chi(L(G^k))$? $\endgroup$
    – joro
    Commented Jul 8, 2015 at 7:40
  • $\begingroup$ I believe $\chi(L^k(G))$ is fine. Working with $L^2(G)$ makes sense for the strong edge coloring - it doesn't have to be a line graph. Intuitively, say you have edges $ab, bc, cd$. Then $ab$ and $cd$ cannot be in the same class of a strong edge coloring because of $bc$. But in $L(G)$, $ab$ and $cd$ are not adjacent, so a vertex coloring could put them in the same class. In $L^2(G)$, $ab$ and $cd$ now share an edge, preventing them from being in the same class. $\endgroup$ Commented Jul 8, 2015 at 14:50
  • $\begingroup$ Ok, it doesn't need be line graph indeed. Thanks. $\endgroup$
    – joro
    Commented Jul 9, 2015 at 13:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .