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

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?

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

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.