# Upper bound for chromatic number of graphs with $\omega(G)\leq\lfloor\frac{\Delta(G)+1}{2}\rfloor+1$

Let $G$ be a simple graph such that $\omega(G)\leq\lfloor\frac{\Delta(G)+1}{2}\rfloor+1$ where $\Delta(G)$ is the maximal degree of $G$. Is it true that $$\chi(G)\leq \lfloor\frac{\Delta(G)+1}{2}\rfloor+2?$$ A similar problem can be found here, where, ignoring the exceptional case of odd cycles, it is conjectured that

Conjecture (Reed). For any graph $G$ of maximum degree $\Delta(G)$, $\chi(G)$ is at most $\lceil\frac{\Delta(G)+1+\omega(G)}{2}\rceil$.

UPDATE: In the case of graphs that satisfy $\omega(G)\leq\lfloor\frac{\Delta(G)+1}{2}\rfloor+1$, the statement in my problem is stronger than Reed's conjecture. For example suppose $\Delta=100$ and $\omega=50$; then by Reed's conjecture we need $76$ colors, while if my conjecture is true, we need just $52$ colors!

• I think there are triangle free graphs which have $\chi(G)=n$ at any $n$. If $\Delta(G)$ is degree then it could be true. – T.... Oct 12 '17 at 14:22
• @PeterHeinig, Thank you for your precision. – C.F.G Oct 14 '17 at 9:42
• It seems useful to note: the conj. mentioned in OP is among the most notorious conjectures in graph theory. Idea is that (0) trivially, the class function $\chi\colon\mathsf{Graphs}\to\omega$ is a convex combination of its obvious lower bound $\omega(.)\colon\mathsf{Graphs}\to\omega$ and its obvious upper bound $\Delta(.)+1$, since $0\cdot x+1\cdot y$ is a convex combination, (1) (King-)Reed proved $\exists\varepsilon>0$ s.t. $\epsilon\cdot \omega+ (1-\epsilon)\cdot(\Delta+1)$ is a bound for $\chi$ too, (2) Reed's conj. is that $\epsilon:=\frac12$ works (it's open, and a bit 'hopeful'). – Peter Heinig Oct 18 '17 at 7:21

As far as I know, your conjecture is an open problem, because Reed's conjecture is still open for $\omega=2$. For $\omega=2$, your conjecture is essentially equivalent to Reed's conjecture. That is, up to rounding, both conjectures assert that every triangle-free graph has chromatic number at most $\Delta/2+2$.

As mentioned by Fedor Petrov, a bound of $9\Delta / \log \Delta$ was proved by Johansson (even for the list version) in this case.

One can try to lower the constant term of $9$, by restricting to large $\Delta$. The state of the art in this direction is a recent paper of Mike Molloy who proves that for every $\epsilon >0$, there exists $\Delta_\epsilon$ such that every graph triangle-free $G$ with maximum degree at least $\Delta_\epsilon$ has list chromatic number at most $(1+\epsilon) \frac{\Delta(G)}{\log \Delta(G)}$.

On the other hand, if we only want a linear bound in $\Delta$, but with the constant term optimized, the best result (as far as I know) is by Kostochka. He proved that triangle-free graphs have chromatic number at most $2\Delta/3+2$. I could not track down a reference, but this is well-known. See for example, Section 2.3 of Andrew King's PhD thesis.

In summary, your conjecture is not known to be true even for $\omega=2$.

• Thanks @Tony Huynh. Could you please provide a link of Kostochka paper? – C.F.G Oct 13 '17 at 6:29
• Hm, is not it proved that $\chi=O(\Delta/\log \Delta)$ in triangle-free graphs, which is better for large $\Delta$? – Fedor Petrov Oct 13 '17 at 6:54
• @FedorPetrov Yes, that is true, thanks. Regarding the conjecture, in describing partial results, I thought it was more natural to try to get a linear bound, but with the constant optimized. I edited in more information now. – Tony Huynh Oct 13 '17 at 12:46
• Kostochka's slightly stronger result is that any triangle-free graph has $\chi(G)\leq2\lceil\frac{\Delta+2}{3}\rceil$, which for $\Delta\equiv 0$ or $\Delta\equiv 1$ modulo 3 is equivalent to the bound $2\Delta/3+2$ given in this answer, but whenever $\Delta\equiv 2\ (\mathrm{mod}\ 3)$ Kostochka's bound equals $<\lfloor2\Delta/3+2\rfloor\color{red}{-1}$, hence slightly stronger. – Peter Heinig Feb 25 '18 at 17:08
• Getting back to the bibliographic challenge, let me add that even Jensen and Toft seem not to have been able to access the paper, and in their book [T. R. Jensen, B. Toft, Graph Coloring Problems, John Wiley & Sons, 2011, ISBN 9781118030745] on page 83 write "The proof was published by the Russian Academy of Sciences in Novosibirsk in 1982, but it is not generally accessible." I have written to a few people in Russia, but they didn't have access to it either. Maybe an MO-user in Russia can help out. – Peter Heinig Feb 25 '18 at 17:11

The probabilistic construction for showing Reed's conjecture is best possible disproves this conjecture. For example, at the end of this paper, using the construction with $n = \frac23 \Delta$ will give you counterexamples.

• What are the $n$ and $\Delta$? in usual notation we must have $\Delta< n$. – C.F.G Nov 25 '17 at 8:08
• The construction begins with the paragraph "We will randomly construct a graph $H$ on $n$ vertices..." at the bottom of page 22 of the paper linked by Ztas Nellets. Note that $n$ is not the number of vertices in the final constructed graph $G$, which is formed by joining $H$ to $K_{\Delta+1-n}$ and so has $\Delta+1$ vertices. It's not hard to see that with high probability $\Delta$ does indeed end up being the maximum degree of $G$. – j.c. Nov 25 '17 at 13:36

i can't comment yet, but the answer of Ztas Nellets is correct, this conjecture is false, the probabilistic construction in my linked paper with Cranston is from Reed's discussion of variants and tightness of his conjecture.

In regards to the paper of Kostochka, i proved a generalization here https://doi.org/10.1002/jgt.21634 which also implies the slightly stronger result Peter Heinig mentions. The proof is essentially the same as Kostochka's original in the paper nobody can find (i had a hardcopy at some point, but cannot find it).