Skip to main content
1 of 3
Felix Goldberg
  • 7k
  • 4
  • 31
  • 55

Okay, I think I can show that $\chi \leq 5$ for the second graph on verret's list.

Using Iglin's wonderful matlab package for graph theory (http://www.mathworks.com/matlabcentral/fileexchange/4266) I found out that its independence number is $\alpha=10$.

In a recent paper (http://www.sciencedirect.com/science/article/pii/S0012365X09002842) Kohl & Schiermeyer have shown that Reed's conjecture holds for graphs with $\Delta \geq n - \alpha -4$.

QED

Felix Goldberg
  • 7k
  • 4
  • 31
  • 55