<p>Found this from graphclasses.org.</p>

<p>Two papers give conflicting results for coloring <a href="http://graphclasses.org/classes/gc_396.html" rel="nofollow">$P_5$-free</a>
graphs  which appear to imply $P=NP$.</p>

<p>From <a href="http://www.researchgate.net/publication/1959697_Polynomial-time_algorithm_for_vertex_k-colorability_of_P_5-free_graphs" rel="nofollow">Polynomial-time algorithm for vertex k-colorability of P_5-free graphs</a></p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>From <a href="http://www.sciencedirect.com/science/article/pii/S0012365X05001019" rel="nofollow">Some new hereditary classes where graph coloring remains NP-hard, p 5</a></p>

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

<p>$2K_2-free \subset P_5-free$ and the other class contains $P_5$.</p>

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

<p>Question:</p>

<blockquote>
  <p>What is wrong with this seeming contradiction?</p>
</blockquote>

CC BY-SA 3.0
2015-07-10T11:24:43.647Z
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
<cc.complexity-theory><graph-theory><graph-colouring><graph-classes>
Two paper appear to imply collapse via coloring $P_5$-free graphs
joro
# Two paper appear to imply collapse via coloring $P_5$-free graphs

(Asked by: username_0 on 2015-07-10)

Found this from graphclasses.org.

Two papers give conflicting results for coloring [$P\_5$-free](http://graphclasses.org/classes/gc_396.html)
graphs which appear to imply $P=NP$.

From [Polynomial-time algorithm for vertex k-colorability of P\_5-free graphs](http://www.researchgate.net/publication/1959697_Polynomial-time_algorithm_for_vertex_k-colorability_of_P_5-free_graphs)

> 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.

From [Some new hereditary classes where graph coloring remains NP-hard, p 5](http://www.sciencedirect.com/science/article/pii/S0012365X05001019)

> ... 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?

**Tags:** cc.complexity-theory, graph-theory, graph-colouring, graph-classes
> **Comments:**
> **username_1**: 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.  

---

## 0 answers

