But if $n=2$, and $G=P_3=a-b-c$, $C_1=\{b\}$, $C_2=\{a,c\}$, isn't $e(C_2,V \setminus C_2) = e(C_2,C_1)=2 > 8-7$ ?

Hmmm yes, I keep getting mixed up :). Thank you Fedor!

Shouldn't the Lemma be if $G$ satsifies $\chi= \chi_1$ then $e(C_i,V \setminus C_i) \color{red}{\ge} 4n-7$?

In case 2.1, how do you count the number of edges in $G\setminus \{b,c\}$?

I'm still processing your proof, but I like how the cases from here re appear. Out of curiosity were you inspired by the other (incomplete) proof, or did you restart from scratch ?

@FedorPetrov Thanks for your input. I am not sure I follow. In particular, what is $\chi(f(\chi)-f(\chi-1))$ ? The part inside $\chi()$ should be a graph, but $f(\chi)-f(\chi-1)$ is an integer.. (?) Please feel free to elaborate.

@MartinRubey I have noticed that there are $1200$ graphs for which $\chi_1$ is given, but only $208$ for $\chi$ (and btw $578$ for $m$). Do you think it would be possible to update the data base in order to have access to $\chi$ (and $m$) for all $1200$ graphs ? Of course the chromatic number can be computed by changing the right hand term of the last constraint to $0$.

Yes indeed ! This is precisely the graph that was sketched which gave birth to the conjecture.

@MartinRubey I have updated the post with some results from the data available on findstats.org. The conjecture holds for the graphs in findstats.

@MartinRubey Thanks for the additional info. At first sight, the values look right. I will analyze and compare with the stats of the chromatic number and post it here.

@MartinRubey Thanks for that, this is very interesting! I will take a look. I wasn't aware of FindStat and I like the concept, great work. May I ask: 1/ what solver is used behind the curtains in FindStat ? 2/ What is the best way to visualize the stats ? The values section ? Is there any form of agregation of the results ?