Conjecture on minimum size of graph

Question

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.

Answer 1

We prove that, indeed, whenever graph $G=(V,E)$ is $n$-colorable and has less than $2(n-1)^2$ edges, it has 1-improper $(n-1)$-coloring.

Induction by $n$, base $n=1$, $n=2$ is clear. So we assume that $n>2$ and the claim is proved for all smaller values of $n$, but does not hold for our $G$.

Consider the $n$-coloring, denote the colors $1,\ldots,n$, corresponding color classes $C_1,\ldots,C_n$, so $V=\sqcup C_i$. For disjoint subsets $V_1,V_2\subset V$ we denote by $E(V_1,V_2)$ the set of edges between $V_1$ and $V_2$ and by $e(V_1,V_2):=|E(V_1,V_2)|$ the number of such edges. We also relax these notations to $E(v,V_2)$ if $V_1=\{v\}$, and so on.

Note that if $E(C_i,C_j)$ for some $i\ne j$ does not contain two edges with common endpoint, we may construct a 1-improper coloring just by uniting colors $i$ and $j$. So this is not the case, in particular $e(C_i,C_j)\geqslant 2$. We start with

Lemma. $e(C_i,V\setminus C_i)\leqslant 4n-7$ for every $i=1,\ldots,n$.

Proof. Assume the contrary: $e(C_i,V\setminus C_i)\geqslant 4n-6$. Then the graph induced on $V\setminus C_i$ has less then $2(n-1)^2-(4n-6)=2(n-2)^2$ edges. By induction proposition it has a 1-improper $(n-2)$-coloring. Add $C_i$ colored with $(n-1)$-st color, and get a 1-improper $(n-1)$-coloring of $G$. A contradiction.

Consider several cases.

1. $e(C_i,C_j)=2$ for some $i\ne j$. Say, $i=1$, $j=2$, $E(C_1,C_2)=\{ac,bc\}$ for $a,b\in C_1$, $c\in C_2$. Assume that $e(b,C_i)<2$ for certain $i>2$. Then we may recolor $b$ to color $i$, $C_1\setminus \{b\}$ to color 2 and obtain a 1-improper $(n-1)$-coloring. Thus $e(b,C_i)\geqslant 2$ for all $i>2$, analogously $e(a,C_i)\geqslant 2$. Therefore $e(C_1,C_i)\geqslant 4$, and $e(C_1,V\setminus C_1)\geqslant 2+4(n-2)=4n-6$ that contradicts to Lemma.

2. $e(C_i,C_j)=3$ for some $i\ne j$, but not all 3 edges of $E(C_i,C_j)$ share a common endpoint. Say, $i=1$, $j=2$, $E(C_1,C_2)=\{ac,bc,e\}$, where $a,b\in C_1$, $c\in C_2$, $e$ is not incident to $c$ and to $a$ (but $e$ may be incident to $b$ or not). Assume that $e(c,C_i)<2$ for certain $i>2$. Then recoloring $c$ to $i$, $C_2\setminus \{c\}$ to 1 we get a 1-improper $(n-1)$-coloring of $G$, that is impossible. Analogous recoloring works if $e(b,C_i)<2$. Thus $e(\{b,c\},C_i)\geqslant 4$ for all $i\geqslant 3$. Consider two subcases.

2.1) $e$ is incident to $b$. Then $G\setminus \{b,c\}$ is $(n-1)$-colorable (unite colors 1 and 2 in our coloring of $G$), and has less than $2(n-1)^2-3-4(n-2)<2(n-2)^2$ edges. Thus it has a 1-impoper $(n-2)$-coloring and we may add $\{b,c\}$ with extra color to get a 1-improper $(n-1)$-coloring of $G$.

2.2) $e=uv$, $u\in C_1\setminus \{a,b\}$, $v\in C_2\setminus \{c\}$. Then for every $i>2$ we have $e(a,C_i)\geqslant 1$, $e(u,C_i)\geqslant 1$: otherwise recolor $a$ or $u$, correspondingly, to color $i$, and get a case 1). Totally $e(C_1,C_i)\geqslant 4$, and $e(C_1,V\setminus C_1)\geqslant 3+4(n-2)=4n-5$, that contradicts to Lemma.

3. $e(C_i,C_j)=3$ for certain $i\ne j$ and all edges of $E(C_i,C_j)$ share a common endpoint. Say, $i=1$, $j=2$, $E(C_1,C_2)=\{ad,bd,cd\}$, where $a,b,c\in C_1$, $d\in C_2$. Recolor $C_2\setminus \{d\}$ to color 1. Now $C_2=\{d\}$. Assume that still $e(C_i,C_j)=3$ for certain $i,j$ different from 2. Then the edges from $E(C_i,C_j)$ share a common endpoint (since case 2 is already considered), let this endpoint $v$ belong to $C_j$. Thus we may make $|C_j|=1$ by recoloring $C_j\setminus \{v\}$ to color $i$. Now we have two color classes $2,j$ of size 1 that contradicts to $e(C_2,C_j)\geqslant 2$. Therefore it remains to consider case

4. $e(C_i,C_j)\geqslant 4$ whenever $i\ne j$ and $2\notin \{i,j\}$. Then $|E|=\sum_{i<j} e(C_i,C_j)\geqslant 3(n-1)+4{n-1\choose 2}>2(n-1)^2$, a contradiction.

Answer 2

Let us prove that any graph with $\chi_1(G)>n$ has at least $2n^2$ edges (with no assumptions on $\chi(G)$). This provides a sharp estimate (and the method also shows how to construct an optimal graph).

Lemma. Assume that the maximal degree in $G$ does not exceed $2k-1$. Then $\chi_1(G)\leq k$.

Proof. Consider a coloring in $k$ colors with the smallest number of monocolor edges. Assume that a vertex $v$ has two neighbors of its color $c$; then there is a color $c’$ appearing among the neighbors of $v$ at most once. Recoloring $v$ with $c’$ decreases the number of monocolor edges. This contradiction proves the Lemma.

Back to our statement. Induction on $n$. The base case $n=0$ is trivial. For the step, arguing indirectly, assume that $G$ has less than $2n^2$ edges but $\chi_1(G)>n$. Find a vertex $v_1$ with $d(v_1)\geq 2n$ (otherwise apply the Lemma).

Next, in $G-v_1$ find a vertex $v_2$ of degree at least $2n-2$ (otherwise, color $G-v_1$ in $n-1$ colors $1$-improperly and color $v_1$ with the $n$th color). Then $G-v_1-v_2$ has less than.$2n^2-2n-(2n-2)=2(n-1)^2$ edges, so $\chi_1(G-v_1-v_2)\leq n-1$ by the inductive hypothesis. It remains to color $v_1$ and $v_2$ with the $n$th color to get a $1$-improper coloring of $G$.

Remark. In the same manner, one can obtain an estimate for $e(G)$ in terms of $\chi_m(G)$.