**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](https://en.wikipedia.org/wiki/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](https://mathoverflow.net/questions/283328/upper-bound-for-chromatic-number-of-graphs-with-omegag-leq-lfloor-frac-delt) 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](https://mathoverflow.net/questions/283328/upper-bound-for-chromatic-number-of-graphs-with-omegag-leq-lfloor-frac-delt); 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.



Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?
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.)


