1
$\begingroup$

From Brooks' Theorem, we know that

if a graph $G$ satisfies that $\Delta (G)=4$ and there is no $5$-clique in $G$, then $\chi (G)\leq 4$.

And it is easy to find a counterexample to the following:

if a graph $G$ satisfies that $\Delta (G)=4$ and there is no $4$-clique in $G$, then $\chi (G)\leq 3$.

I want to ask whether the following conclusion is right or please give a counterexample!

if a graph $G$ satisfies that $\Delta (G)=4$ and there is no $3$-clique in $G$, then $\chi (G)\leq 3$.

$\endgroup$
3
  • 1
    $\begingroup$ It's Brooks's theorem, not Brook's. $\endgroup$
    – bof
    Mar 4, 2015 at 3:04
  • 3
    $\begingroup$ No, it is Brooks' Theorem. $\endgroup$
    – David Wood
    Mar 4, 2015 at 6:41
  • 1
    $\begingroup$ Blass's opinion agrees with @bof's. $\endgroup$ Mar 4, 2015 at 14:38

1 Answer 1

1
$\begingroup$

The statement is false.

Try this in Sage:

g = Graph("K?BD@hWFf_HW")
g.show()

enter image description here

Then

g.chromatic_number()

to confirm.

In general, it seems that imposing "triangle-free" does not seem to materially alter the chromatic behaviour of a class of graphs.

$\endgroup$
3
  • 2
    $\begingroup$ Johansson proved that every triangle-free graph with maximum degree $\Delta$ is $O(\Delta/\log\Delta)$-colourable. $\endgroup$
    – David Wood
    Mar 4, 2015 at 6:40
  • $\begingroup$ Thank you very much for your counterexample!Gordon Royle. Would you please look at this question: mathoverflow.net/questions/198811/… and give a counterexample? $\endgroup$
    – user173856
    Mar 4, 2015 at 8:52
  • $\begingroup$ This is the Mycielski graph of $C_5$. $\endgroup$ Mar 5, 2016 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.