Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6? Question. Does there exist a graph $G$ with $(\Delta(G),\chi(G),\omega(G))=(8,8,6)$?
Remarks.
Here, 


*

*'graph'='undirected simple graph'='irreflexive symmetric relation on a set'

*any number of vertices is permitted in the question (though, trivially, at least 8 vertices (and quite a bit more) vertices are necessary

*finiteness of the graph is not required, but finite graphs are the main focus

*$\Delta(G)$ $=$ maximum vertex degree of $G$

*$\chi(G)$ $=$ chromatic number of $G$

*$\omega(G)$ $=$ clique number of $G$

*Needless to say, what I am asking for is not ruled out by the trivial bounds $\omega\leq\chi\leq\Delta+1$. One should also note that what I am asking for can be regarded as a 'critical instance' for Brooks' theorem (since $(\chi(G),\omega(G))=(8,6)$ by itself implies that $G$ is neither a complete graph nor a circuit, Brooks theorem applies and guarantees that $\chi(G)\leq 8$, hence what is being asked is an explicit example of a graph achieving Brooks' bound; what seems to make it difficult is that the clique number is required to be six.)

*Needless to say, the condition that $\Delta(G)=8$ rules out most of the 'usual' 'named graphs (e.g., all strongly regular graph that the English Wikipedia currently lists as a named example are not 8-regular, so do not satisfy $\Delta(G)=8$

*While I won't go into details to try to 'prove' that I did, I think I did try quite a few things to find an example.

*This question is motivated both by research on triangle-free graphs (of course, there, $\omega=2)$ and in particular by my writing a comprehensive answer to this interesting research question of 'C.F.G.'. I seem to need a graph as in the question, to make my answer 'more complete', if that's grammatically possible. The particular instance in the question isn't really necessary to my answer, but it would be very nice to have a construction, or proof of non-existence of, such a graph.

*Let me also mention that constructions of, or proofs of impossibility of, graphs $G$ with 

(axiom.0) $\quad\Delta(G)\geq 8$
(axiom.1)  $\quad\omega(G)\leq\lceil\frac12\Delta(G)\rceil+2$
(axiom.2)
$\begin{cases}
  3+\frac12\Delta(G)\hspace{25pt} < \quad\chi(G)\quad \leq 2+\frac34(\Delta(G)+0) & \text{if $\Delta(G)\ \mathrm{mod}\ 4\quad = 0$ }  \\
  2+\frac12(\Delta(G)+3) < \quad\chi(G)\quad \leq 2+\frac34(\Delta(G)+3) & \text{if $\Delta(G)\ \mathrm{mod}\ 4\quad = 1$ }  \\
  3+\frac12\Delta(G)\hspace{25pt} < \quad\chi(G)\quad \leq 0+\frac34(\Delta(G)+2)  & \text{if $\Delta(G)\ \mathrm{mod}\ 4\quad = 2$ } \\ 
  3+\frac12(\Delta(G)+1) < \quad\chi(G)\quad \leq 1+\frac34(\Delta(G)+1) & \text{if $\Delta(G)\ \mathrm{mod}\ 4\quad = 3$ }
 \end{cases}$

would be helpful for writing the answer to C.F.G.'s question, too, though I chose to make the actual question simpler, by picking out the instance $\Delta(G)=8$, whereupon the first line of the cases above becomes $7<\chi(G)\leq8$, equivalently, $\chi(G)=8$. Note also that then $\lceil\frac12\Delta(G)\rceil+2=6$, explaining the $\omega$-value in the question. 


*

*Again, an answer to the present answer does not simply imply an answer to the cited thread; I am not asking someone else's question be answered again here; the present question arises as a relevant technical sub-issue in my answer. 

*For the above more general specification of graphs, planar graph evidently are no solution (since they have $\chi(G)\leq4$), and dense random graphs are not a solution either because, very roughly speaking, for them asymptotically almost surely (axiom.1) is satisfied but (axiom.2) is not (because, very very roughly, $G(n,\frac12)$ has  $\Delta\in\Theta(\frac12 n)$ but $\chi\in\Theta(\frac{n}{\log n})$, making it impossible to satisfy the lower bound in (axiom.2). Results of McDiarmid, Müller and Penrose make it possible to 'try out' random geometric graphs, but for those, sadly, again not all axioms seem to be satisfied (though getting comprehensible results on the maximum degree in random geometric graph seems to be difficult). 

*Random regular graphs also do not provide an answer, e.g. because [Coja-Oghlan--Efthymiou--Hetterich: On the chromatic number of random regular graphs Journal of Combinatorial Theory, Series B, 116:367-439] implies that for this it is necessary that $8 \geq (2\cdot 8-1)\log(8) - 1$, which is false.
 A: The example given by Fedor Petrov is well-known and so is the generalization mentioned by Peter Heinig. Another way to view it is as the line graph of a 5-cycle with all tripled edges. The first appearance i know of was in the 1970s, used by Paul Catlin in his counterexample to the Hajos conjecture https://doi.org/10.1016/0095-8956(79)90062-5
The example with $\chi=\Delta=8$ and $\omega=6$ is also the only known (connected) counterexample to the Borodin-Kostochka conjecture for $\Delta=8$.
The more general examples prove tightness of a conjecture on the chromatic number of vertex transitive graphs  Cranston and i made: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p1
That conjecture is that vertex transitive graphs with $\chi > \omega$ have $\chi \le (5\Delta + 8) / 6$.  This is proved fractionally and the full conjecture follows from Reed's conjecture combined with the strong coloring conjecture. The conjecture is open even for Cayley graphs.
Another related conjecture that the example shows tightness for given by Cranston and i in http://epubs.siam.org/doi/abs/10.1137/130929515
is that graphs with $\omega < \Delta - 3$ have $\chi < \Delta$. We prove this for $\Delta \ge 13$.  The remaining open cases are $\Delta = 6,8,9,11,12$.
Another way to say that is that the OP's question is open in the cases:
(6,6,3),
(8,8,5),
(9,9,6),
(11,11,8),
(12,12,9).
A: Yes, it exists. Take 5 triangles $T_1,\dots,T_5$ (all 15 vertices are distinct) and draw also all edges between $T_i$ and $T_{i+1}$, $i=1,2,3,4$, and between $T_5$ and $T_1$. All degrees are equal to 8, maximal clique is formed by two neighboring triangles, and $\chi=8$. Indeed, each color may appear at most twice (in at most two triangles), thus 7 colors are not enough. But 8 colors are of course enough (by Brooks theorem, if you want.)
