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

Relevant footnotes to Fedor Petrov's nice, helpful, and completely correct answer.

Fedor's answer seems essentially unimprovable both in brevity and completeness (it's all there).

I hadn't expected such an elegant solution to exist, rather looked in the more complicated directions like sparse or dense random graphs, random regular graphs, and general Mycielskians. None of these gives an example.

I would like to point out a few little things nevertheless, to make this thread more usesul as a reference.

0. The correct technical term. Fedor's construction is simultaneously

• the lexicographic product $C^5\circ K^3$

• the strong product $C^5\boxtimes K^3$

of the 5-circuit with the 3-circuit $K^3\cong C^3$. That the same graph is named by two (in general: very different) technical terms is true for a general reason: it is evident from the definitions that

for every graph $G$ and every cardinal $\kappa$ we have $G\circ K^\kappa = G\ {\scriptsize\text{$\boxtimes$}}\ K^\kappa$

(This is a strict equality of sets, not only a graph-isomorphism.)

1. An illustration of the example in the accepted answer.

The above represents a graph with isomorophism type $C^5\circ K^3$. The blue expressions are vertex labels, created according to a self-explanatory rule. The green numerals represent a proper vertex-$8$-coloring of $C^5\circ K^3$. Representing the coloring this way seems the best way to also make it clear that such a coloring corresponds to a 5-circuit withing the Kneser graph $K(8,3)$, since (to me) the most usual way to represent an eight-element set is the finite ordinal $8=\{0,1,\dotsc,7\}$.

2. Two alternative proofs of the lower bound $\chi(C^5\circ K^3)\geq 8$. Fedor's proof of $\chi(C^5\circ K^3)\geq 8$ by a counting argument is correct, and arguably the most direct proof imaginable. Nevertheless, I would like to add to it two further proofs (and two near-misses), to add relevant context.

Lemma. $\chi(C^5\circ K^3)\geq 8$.

First proof (the counting argument in the accepted answer). Since no two colors can be used in the same $K^3$, every color-class in any hypothethical proper coloring projects (under the canonical epimorphism $C^5\circ K^2\to C^5$ to an independent set in $C^5$, and since $C^5$ has independence number $2$, it follows that every color can be used at most 2-times in any proper coloring, so if there were $\leq 7$ colors, there were $\leq 7\cdot 2 = 14 < 15 = \lvert V(C^5\circ K^3)\rvert$ colored vertices in total, which is impossible. $\hspace{250pt}$ $\Box_{\text{First proof}}$

Second Proof (via a Theorem of Klavžar-Yeh). By Theorem 6 on p. 238 of

Sandi Klavžar's, Hong-Gwa Yeh: On the fractional chromatic number, the chromatic number, and graph products. Discrete Mathematics 247 (2002) 235-242

it is known that

for all graphs $G_0,G_1$ we have $\chi(G_0\circ G_1)\geq\chi_f(G_0)\cdot\chi(G_1)$

where $\chi_f(\cdot)$ denotes the fractional chromatic number and $\circ$ the lexicographic product.

Moreover, since the 5-circuit is vertex-transitive, Proposition 3.1.1 in

E. R. Scheinermann, D. H. Ullmann: Fractional Graph Theory. Dover Publications (1997)

implies that $\chi_f(C^5) = 5/2$. It follows that

$\chi(C^5\circ K^3)=\chi_f(C^5)\cdot\chi(K^3)=5/2\cdot 3=7.5$

and since $\chi$ by definition is integer-valued, this completes the proof of the lemma. $\hspace{10pt}$ $\Box_{\text{Second proof}}$

Third proof (via a theorem of Stahl). According to Theorem 26.12 in

Hammack-Imrich-Klavžar: Handbook of Graph Products. Second Edition. CRC Press 2011

Saul Stahl in 1976 published a proof that

for all graphs $G_0,G_1$ we have $\chi(G_0\circ G_1)\geq 2\chi(G_1) + \biggl\lceil\frac{ \chi(G_1) }{ \frac12(\mathrm{oddgirth}(G_0)-1) }\biggr\rceil$

hence

$\chi(C^5\circ K^3)\geq 2\chi(K^3) + \biggl\lceil\frac{ \chi(K^3) }{ \frac12(\mathrm{oddgirth}(C^5)-1) }\biggr\rceil = 2\cdot3 + \biggl\lceil\frac{ 3 }{ \frac12(5-1) }\biggr\rceil = 6+\lceil1.5\rceil=8$

proving the lemma. $\hspace{210pt}$ $\Box_{\text{Third proof}}$

Remark on another theorem of Stahl's and on a theorem of Linial-Vazirani, both of which, interestingly, are not strong enough to imply $\chi(C^5\circ K^3)\geq 8$. According to Theorem 26.11 in op. cit., Linial and Vazirani proved the following interesting 'transcendental' bound:

for all graphs $G_0,G_1$ we have $\chi(G_0\circ G_1)\geq \frac{(\chi(G_0)-1)\cdot\chi(G_1)}{\log\ \lvert V(G_0)\rvert}$

In the present situation (because of the very small numbers involved), this bound is the weakest of all:

$\chi(C^5\circ K^3)\geq \frac{(\chi(C^5)-1)\cdot\chi(K^3)}{\log\ \lvert V(C^5)\rvert} = \frac{(3-1)\cdot 3}{\log 5} = \frac{6}{\log 5}$

and because of $\frac{6}{\log 5} < 6$, this bound only implies $\chi(C^5\circ K^3)\geq 6$, but does not imply $\chi(C^5\circ K^3)\geq 8$.

Interestingly, while one result of Stahl's did prove $\chi(C^5\circ K^3)\geq 8$, another, mentioned only one page earlier in Hammack-Imrich-Klavžar, does not prove it: according to Theorem 26.9 on p. 321 of op. cit.

for all graphs $G_0,G_1$ we have $\chi(G_0\circ G_1)\geq \chi(G_0) + 2\chi(G_1)-2$

so $\chi(C^5\circ K^3)\geq \chi(C^5) + 2\chi(K^3)-2 = 3 + 2\cdot 3-2 = 7$, so this bound only proves $\geq 7$, not $\geq 8$.

It seems useful to list all the lower bounds again:

(four.lower.bounds.for.lex.prod) for arbitrary finite graphs $G_0,G_1$ we have $\chi(G_0\circ G_1)\geq\max\begin{cases} \chi_f(G_0)\cdot\chi(G_1) \hspace{145pt} =: \mathrm{frac.bound}(G_0,G_1) \\ 2\chi(G_1) + \biggl\lceil\frac{ \chi(G_1) }{ \frac12(\mathrm{oddgirth}(G_0)-1) }\biggr\rceil \hspace{70pt} =: \mathrm{oddgirth.bound}(G_0,G_1)\\ {\large\frac{(\chi(G_0)-1)\cdot\chi(G_1)}{\log\ \lvert V(G_0)\rvert} }\hspace{95pt} =: \mathrm{transcendental.bound}(G_0,G_1)\\ \chi(G_0) + 2\chi(G_1)-2\hspace{116pt} =: \mathrm{linear.bound}(G_0,G_1) \end{cases}$

According to my own 'feel' for what is off-thread and what is not, I think that this is the appropriate point to stop and not discuss the interesting topic of

whether the four lower bounds given (four.lower.bounds.for.lex.prod) for $\chi$ are mutually-independent w.r.t. semantic-entailment relative to the class of all finite graphs;

that is to say,

whether for each of the 24 permutations $\sigma\in\mathrm{Sym}(\text{frac},\text{oddgirth},\text{transcendental},\text{linear})$ there exists at least one $(G_0,G_1)\in\mathsf{FiniteGraphs}\times\mathsf{FiniteGraphs}$ such that

$\sigma(\text{frac}).\text{bound}(G_0,G_1)$

$<$

$\sigma(\text{oddgirth}).\text{bound}(G_0,G_1)$

$<$

$\sigma(\text{transcendental}).\text{bound}(G_0,G_1)$

$<$

$\sigma(\text{linear}).\text{bound}(G_0,G_1)$.

Hammack-Imrich-Klavžar apparently do not address this obvious question. Doing so here seems excessive.

3. Relevance of Fedor's answer to Reed's omega-Delta-chi conjecture.

It seems worth pointing out that

Fedor's example can be generalized to construct infinitely-many isomorphism types of graphs for which Reed's notorious, incredible-yet-unrefuted omega-Delta-chi-conjecture holds with equality. I expect that this family of examples has been described in the literature already but I could not find it anywhere and would appreciate a relevant comment if someone happens to know whether this has been recorded somewhere before (I will^(UPDATE) then record this here, for completeness):

For any finite cardinal $k$,

• $\omega(C^5\circ K^k) = 2k$

• $\Delta(C^5\circ K^k) = k + (k-1) + k = 3k-1$

• $\chi(C^5\circ K^k)$ $\geq$ ( using $\text{frac.bound}(G_0,G_1)$ ) $\geq$ $\chi_f(C^5)\cdot\chi(K^k)$ = $\frac52\cdot k$

hence, because of $\chi$ being integer valued,

$\chi(C^5\circ K^k)\geq \lceil\frac52 k\rceil$.

Update: I am grateful to 'landon rabern' for pointing out that this lower bound always holds with equality, and also pointing out a reference; see the footnote.

Turning to Reed's conjectural upper bound, abbreviating $G:= C^5\circ K^k$, we have

$\lceil\frac{\omega(G)\ +\ \Delta(G)+1}{2}\rceil = \lceil\frac{\omega(G)\ +\ \Delta(G)+1}{2}\rceil = \lceil\frac52 k\rceil$

which is equal to the actual value of $\chi(C^5\circ K^k)$. We have shown that

for each $k\in\omega$, (the straightforward generalization of) Fedor's construction is an example of Reed's upper bound holding with equality.

Motivated by this interesting answer of Fedor's, I stopped to spend a few hours on trying to find a counterexample to Reed's conjecture, by varying Fedor's construction, but to no avail.

It seems that as soon as one 'strays' from the construction of the form

(5-circuit)lexicographicproduct(complete-graph),

Reed's conjectural bound holds with room to spare.

${}$_________________________

^(UPDATE) Many thanks to 'landon rabern' for pointing out a literature-reference of this formula. The reference is

Catlin, Paul A., Hajós graph-coloring conjecture: Variations and counterexamples. J. Comb. Theory, Ser. B 26, 268-274 (1979).

wherein $C^5\circ K^k$ is represented as the line graph of a suitable multigraph. The relevant part of that article is:

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