Proofing Decide Injective Coloring Problem is NP-complete for perfect elimination bipartite graphs?

Question

So the proof goes like this

For a graph $G=(V,E)$, $V=\{v_1,v_2,...,v_n\}$, $E=\{e_1,e_2,...,e_m\}$ having a chromatic number $X(G)$ we construct a perfect elimination bipartite graph $H$, using following steps

1. Subdivide each edge of $G$ to get new vertices ei , $1 ≤ i ≤ m$
2. For each $e_i$, $1 ≤ i ≤ m$, add another vertex $e′_i$ and add edges $e_ie'_j$ for each $i$ and $j$, $1 ≤ i, j ≤ m$.
3. Add pendant vertex $y_i$ and an edge $y_iv_i$ for each $i$, $1 ≤ i ≤ n$.

After this proof goes on to proof that $X(G) ≤ k$ if and only if $X_i (H) ≤ k + |E|$.

$X_i(H)$ is the injective coloring of H.

And concludes that

Therefore, Decide Injective Coloring Problem is NP-complete for perfect elimination bipartite graphs.

I don't get how it came to this conclusion?

Answer 1

The basic idea is that the problem "given a graph $G$ and a number $k$, determine if $\chi(G) \le k$" is a well-known NP-complete problem.

This proof seems to prove that this problem is exactly as hard as the problem "given a perfect elimination bipartite graph $G$ and a number $k$, determine if $\chi_i(G) \le k + |E(G)|$".

So this new problem must also be NP-hard: if we can solve it efficiently, we can solve the $k$-coloring problem efficiently, and from there, we could solve any problem in NP efficiently. Also, the new problem must be in NP; this might be already clear, but if it's not, we know that the $k$-coloring problem is in NP, and can be used to solve this one.

(I can't comment on the specifics, because I'm not sure what an injective coloring is, or on the details of how the proof works.)