17
$\begingroup$

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.

$\endgroup$
37
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

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.

enter image description here

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:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Here is Catlin's dissertation. It was in 1976 and he does not appear to know about this counterexample to the Borodin-Kostochka conjecture for $\Delta=8$ at that time. $\endgroup$ – landon rabern Mar 27 '18 at 11:44
  • 1
    $\begingroup$ Also interesting that Borodin and Kostochka must have known about this example when they made their conjecture, their paper was published in 1977. $\endgroup$ – landon rabern Mar 27 '18 at 12:14
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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