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

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

• Since there is a graph on $5$ vertices with chromatic number $3$ and clique number $2$, it follows that for $k\ge3$ there is a graph on $k+2$ vertices with chromatic number $k$ and clique number $k-1$, right?
– bof
Mar 26, 2022 at 3:49

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