Smallest $K_k$-free graph with chromatic number $\ge k$

Question

It is well known that a (simple undirected) graph $\mathcal G$ may require $k$ or more colors for a proper vertex coloring (adjacent vertices must have different colors) without containing a $k$-clique (complete subgraph on $k$ vertices) when $k \gt 2$. This is often considered in the existence of triangle-free graphs with arbitrarily large chromatic numbers.

My problem is finding the smallest graph $\mathcal G$ (in terms of fewest vertices) with chromatic number $\chi(\mathcal G) \ge k$ which is $K_k-free$ (clique number $\omega(\mathcal G) < k$). See Misha Lavrov's Answer to this Question about the $k=5$ case.

This Question is motivated by a recent one Coloring a Generalized Latin Square in which it might be desired to reach chromatic number $k+1$ (in the off-diagonal entries of the $k\times k$ array considered there) without a clique number higher than $k$.

Misha's answer for $k=5$ links to this graph with seven vertices. It "glues" five tetrahedra ($4$-cliques) together around a common edge. This might suggest constructions for $k\gt 5$.

Answer 1

Though we can think of the graph in question,

as $5$ tetrahedrons glued together, it is more profitable to think of it as $C_5 + K_2$, where $+$ denotes graph join: we take disjoint copies of $C_5$ and $K_2$, and draw all the edges between them. In the diagram, $C_5$ is the $5$ outside vertices, and $K_2$ is the two center vertices.

Similarly, the graph $C_5 + K_n$ has chromatic number $n+3$ (you need $3$ colors to color $C_5$, and $n$ separate colors to color $K_n$) and clique number $n+2$ (at most two vertices from $C_5$, plus at most $n$ vertices from $K_n$, can be part of a clique). So $C_5 + K_{k-3}$ is a graph with the property you want.

In fact, it is the smallest such graph. $C_5 + K_{k-3}$ has $k+2$ total vertices, so there's only a few cases to check:

• With $k$ vertices, either the graph is $K_k$ (and the clique number is too high) or a proper subgraph of $K_k$ (and the chromatic number is too low).
• With $k+1$ vertices, we need to have minimum degree at least $k-1$ (otherwise, delete a vertex of degree less than $k-1$, $(k-1)$-color the remainder due to the previous bullet point, and color the vertex you deleted with any color not used on its neighbors). So the complement has maximum degree $1$: our graph is a $K_{k+1}$ with some independent edges deleted. If we delete just one edge, the graph still contains $K_k$; delete two edges, and it is now $(k-1)$-colorable.

The argument is basically the same as for $C_5 + K_2$.