Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way of looking at this is that you are allowed to remove any matching from $G$).
It is fairly easy to prove that a graph that satisfies $\chi_1=\chi$ has at least $2\chi-1$ vertices (a proof by induction exists).
However, determining the minimum number of edges in order for the equality to hold seems more difficult.
Quick drawings suggest the number of edges must be larger than $2(\chi-1)^2$, but I cannot manage to prove it. Any suggestions?
Note: it is easy to see that the number of edges must be larger than $\chi(\chi-1)$. Indeed, extremal theory tells us the number of edges in a graph is always larger than $\chi(\chi-1)/2$, but if we can remove any matching, it has to be larger than $\chi(\chi-1)$.
EDIT: please see the spin off of this question here
Disclaimer : the following proof is not valid, but quite close. It may inspire.
For a given $G$ for which $\chi(G) = \chi_1(G)$, first fix a proper coloring with $\chi$ colors. Let $G_i$ be the set of vertices of color $i$. Let $E(i,j)$ be the number of edges between $G_i$ and $G_j$. Note that if for any $i, j$, there were fewer than two edges between $G_i$ and $G_j$, then we could decrease the number of colors by coloring $G_i$ with color $j$, and there would be at most one edge connecting vertices of the same color. So $E(i,j) \ge 2$ for all pairs $i,j$.
Next, suppose that for some $i,j$ we have $E(i,j) < 4$. If the edges between $G_i$ and $G_j$ were pairwise nonadjacent, then again we could simply color $G_i$ with color $j$, and the edges connecting vertices of the same color would be pairwise nonadjacent. So we can ignore those cases. This leaves four possible cases:
Case 1: $a \in G_i, x,y \in G_j, ax, ay \in E$ (the edge set of $G$)
Case 2: $a,b \in G_i, x,y,z \in G_j, ax,ay,bz \in E$
Case 3: $a,b \in G_i, x,y \in G_j, ax,ay,by \in E$
Case 4: $a \in G_i, x,y,z \in G_j, ax,ay,az \in E$
We observe that in any of the four cases, if any of $x, y$, or $z$ were changed to a different color than $i$ or $j$, then the edges of $G_i$ could be changed to other colors while maintaining a 1-improper coloring. In cases 1 and 2, we can color all of $G_i$ with color $j$. In case 3, if $x$ or $y$ is changed to color $k$, then we can change $a$ to color $k$ and all other vertices of $G_i$ to color $j$. In case 4, if $x,y,$ or $z$ get changed to color $k$, we can change $a$ to color $k$ and the rest of $G_i$ to color $j$.
Therefore, it must be impossible to change $x$ and $y$ from the above to different colors. That means for all $k != i,j$, there must be at least two edges from $x$ to $G_k$, and at least two edges from $y$ to $G_k$. So $G(j,k) \ge 4$ for all $k != i,j$.
So, $G(i,j) \ge 4$ for all pairs except a certain set $S$. What we proved above was that if $(i,j) \in S$, then either $i$ or $j$ is precluded from being in any other pair of $S$. So $S$ can have at most $\chi - 1$ pairs. Thus we have
$$ |E| \ge 2(\chi - 1) + 4(\frac{(\chi)(\chi-1)}{2} - (\chi - 1)) = 2(\chi-1)^2. $$
Nice problem!