# Two paper appear to imply collapse via coloring $P_5$-free graphs

Found this from graphclasses.org.

Two papers give conflicting results for coloring $P_5$-free graphs which appear to imply $P=NP$.

Abstract. We give the first polynomial-time algorithm for coloring vertices of P5 -free graphs with k colors. This settles an open problem and generalizes several previously known results.

... Coloring is NP-hard in $2K_2$-free ... and $\{C_5,P_5\} \cup \ldots$-free

$2K_2-free \subset P_5-free$ and the other class contains $P_5$.

According to graphclasses, another reason for hardness is clique cover on the complement (another paper), click +Details for references.

Question:

What is wrong with this seeming contradiction?

• The first paper shows that there exists a function $f$ such that it can be decided if a $P_5$-free graph can be $k$-colored in time $O(n^{f(k)})$. This means that for each fixed $k$, the problem can be solved in polynomial time in $n$. This is an interesting result since the trivial algorithm would use $O(k^n)$ time. However, the result does not give a polynomial time algorithm for CHROMATIC NUMBER of $P_5$-free graphs, since $\sum_{k=1..n} n^{f(k)}$ is not polynomial in $n$. That CHROMATIC NUMBER is NP-hard for $P_5$-free graphs is even mentioned in (the conference version of) the paper.
– JWM
Jul 10, 2015 at 11:24

One of those papers is about k-colorability and the other of
those papers does not specify a constant number of colors.

(For a similar example, consider k-variable-SAT versus SAT.)

• Thank you, but I don't understand. The second paper defines on p.1 "MCP: Find in G = (V , E) a minimum number k of stable sets S1 , . . . , Sk , which cover V (i.e. S1 ∪ · · · ∪ Sk = V ). This minimum number is the chromatic number chi(G) of G.. The quoted result hardness of MCP. In the first paper $k$ is given, so binary search will find minimum $k$. What is wrong with this? According to graphclasses $k$-colorability is NP-hard.
– joro
Jul 10, 2015 at 8:04
• "In the first paper $k$" determines which of [3-coloring,4-coloring,5-coloring,6-coloring,7-coloring,...] is the current problem. $\;$
– user6973
Jul 10, 2015 at 8:24
• Yes, but this is enough. We know $k \le n$. Try $k=2,3,4,...n$ and stop if you find coloring. Each call is polynomial in $n$ and there are at most $n$ calls, which is polynomial in $n$.
– joro
Jul 10, 2015 at 8:26
• Each call being polynomial in $n$ is not enough for their sum to be polynomial in $n$. $\:$ (Consider (n^2)+(n^3)+(n^4)+...+(n^(n-1)).) $\;\;\;\;$
– user6973
Jul 10, 2015 at 8:30
• Max clique is Np-complete. But 2-clique is polynomial time solvable (in $n^2$ time). And we can do 3-clique in $n^3$ time. In fact, for ever fixed k we can solve k-clique in $n^k$ time. But this still doesnt imply P=NP Jul 10, 2015 at 20:00