# Several papers appear to imply P=NP via chordal graphs, what is wrong?

Several papers appear to imply P=NP via chordal graphs, which suggests something is wrong.

As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$ are the independence domination number.

According to VIZINGâ€™S CONJECTURE FOR CHORDAL GRAPHS, p.1

Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.

According to graphclasses.org

In chordal graphs Domination is NP-complete and Independent Domination is polynomial.

The equality in Theorem 1.1 appears to imply P=NP since we can compute $\gamma(G)=i(G)$ in chordal graphs by the above result.

What is wrong with this?

These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:
where $\gamma(G)=2$ and $i(G)=3$.
As a comment, Allan & Laskar showed that $\gamma(G)=i(G)$ when $G$ is claw-free, but there are no such conclusions for chordal graphs.
• So, just to be clear, we're saying that Theorem 1.1 in OP's question is wrong, right? @WillardZahn – Millie Smith Mar 12 '15 at 22:37
• @MillieSmith The paper in the link only claims $\gamma(G)=\gamma^i(G)$, and the one in question is indeed wrong. – Willard Zhan Mar 13 '15 at 1:48