1
$\begingroup$

From Graphs and Digraphs (7 ed)., we have the following exercise:

6.3. For every $k \geq 2$, give an example of a regular $k$-chromatic graph that is not complete.

The examples are clear for $k = 2$ (even cycle) and $k = 3$ (odd cycle), but I have not been able to construct any larger graphs. The best I could do was try an inductive construction, where I assumed a construction existed for graphs with chromatic number less than $k$, and try to build a graph with the desired conditions with $\chi(G) = k$, but I wasn't able to go anywhere with that. How should I approach this problem?

$\endgroup$
2
  • 1
    $\begingroup$ You could take the disjoint union of two complete graphs :) $\endgroup$ Apr 1 at 22:08
  • 1
    $\begingroup$ If you want it to be connected, consider $K_k\square K_2$. $\endgroup$
    – user14111
    Apr 1 at 23:16

1 Answer 1

2
$\begingroup$

The classic solution to this exercise is the complete $k$-partite graph with each part of size $2$, or equivalently $K_{2k}$ minus a perfect matching. It is $2(k-1)$-regular.

$\endgroup$
3
  • $\begingroup$ What makes this solution "classic"? $\endgroup$ Apr 2 at 21:19
  • $\begingroup$ @MishaLavrov It's classic because it's also a Turán graph. $\endgroup$ Apr 3 at 9:51
  • $\begingroup$ In other words, since it is tricky to prove lower bounds on the chromatic number, a natural way to look for answers is to look for graphs that have as many edges as possible: so you start with an arbitrary k-coloring of vertices (e.g. two vertices of each color) and they you add all the allowed edges. (To prove that no better coloring exists, observe that a proper coloring is the same as a partition into independent sets, and the only independent sets here are the original color classes and their subsets.) $\endgroup$ Apr 4 at 15:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .