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

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$.


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.


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).