7
$\begingroup$

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 \begin{equation} \chi(G)\leq \lfloor\frac{\Delta(G)+1}{2}\rfloor+2? \end{equation} 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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Turbo
    Commented Oct 12, 2017 at 14:22
  • 1
    $\begingroup$ @PeterHeinig, Thank you for your precision. $\endgroup$
    – C.F.G
    Commented Oct 14, 2017 at 9:42
  • $\begingroup$ 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'). $\endgroup$
    – Peter Heinig
    Commented Oct 18, 2017 at 7:21

3 Answers 3

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks @Tony Huynh. Could you please provide a link of Kostochka paper? $\endgroup$
    – C.F.G
    Commented Oct 13, 2017 at 6:29
  • 3
    $\begingroup$ Hm, is not it proved that $\chi=O(\Delta/\log \Delta)$ in triangle-free graphs, which is better for large $\Delta$? $\endgroup$
    – Fedor Petrov
    Commented Oct 13, 2017 at 6:54
  • $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    Commented Oct 13, 2017 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Heinig
    Commented Feb 25, 2018 at 17:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Peter Heinig
    Commented Feb 25, 2018 at 17:11
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What are the $n$ and $\Delta$? in usual notation we must have $\Delta< n$. $\endgroup$
    – C.F.G
    Commented Nov 25, 2017 at 8:08
  • 2
    $\begingroup$ 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$. $\endgroup$
    – j.c.
    Commented Nov 25, 2017 at 13:36
2
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .