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 at least $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 (or equals) $\chi(\chi-1)/2$, but if we can remove any matching, it has to be larger than (or equal to) $\chi(\chi-1)$.

Here is a possible MIP formulation for the 1-improper chromatic number $\chi_1(G)$:

### Variables

- $y_c \in \{0,1\}$, takes value $1$ if color $c\in K=\{1,...,n\}$ is used
- $x_{vc}\in \{0,1\}$, takes value $1$ if color $c \in K$ is assigned to node $v \in V$
- $\delta_{uv}\in \{0,1\}$, takes value $1$ if vertices $u$ and $v$ share the same color, $(u,v)\in E$

### Objective Function

$$ \min \; \sum_{c \in K} y_c $$

### Constraints

- One color per node: $$ \sum_{c \in K} x_{vc} = 1 \quad \forall v \in V $$
- If vertex $v$ takes color $c$, $y_c$ is activated: $$ x_{vc} \le y_c \quad \forall v \in V, \forall c \in K $$
- If endpoints of an edge $(u,v)$ share the same color, $\delta_{uv}$ is activated: $$ x_{uc}+x_{vc} \le 1 + \delta_{uv}\quad \forall (u,v) \in E, \forall c \in K $$
- At most one conflict per node: $$ \sum_{u| (u,v)\in E} \delta_{uv} \le 1 \quad \forall v \in V $$

Using data from findstat.org, here is a compilation of results for a few graphs. The conjecture holds for all of the graphs for which the data is available on findstat.org.

**Disclaimer**: This question has been posted here (math.stackexchange) 5 years ago, and has not been answered, so I am trying another community.

However, someone attempted to make a proof, and although the proof is not correct, it may inspire.

13more comments