Intuitive way of constructing a graph with a large chromatic number?

Question

I want to construct a graph with a relatively large chromatic number (10). My only problem is that I can't have K9 (or the complete graph with 9 vertices) as an induced subgraph. Also My edges are at most 6n-12 (where n is the number of vertices). Without dwelling on the details what is one intuitive way I can go about doing this?

Answer 1

I couldn't get clarification via a comment due to insufficient reputation, but I assume the "or" in the parentheses in the second sentence is a typo, since the complete graph on 9 vertices is commonly denoted as $K_9$.

An easy way to do this would be to find a graph $G$ with chromatic number 5 and no induced $K_5$ as subgraph. Now to construct the graph of chromatic number 10 with no $K_9$, simply copy G two times and add all possible edges between the two copies of $G$ (such that when ignoring the edges within the copies of $G$, the vertices form a biclique).

To prove that this new graph has no induced $K_9$, consider that any set of 9 vertices must take at least 5 from one of the copies of $G$. However, $G$ does not contain a $K_5$, hence these 9 vertices cannot form a $K_9$.

To prove that it has chromatic number 10, consider that the colors used in one copy of $G$ must be completely disjoint from those used in the other copy, since we added all possible edges between them. Hence any coloring with less than 10 colors would imply a coloring with less than 5 colors for $G$.

The edge constraint can be easily circumvented by adding isolated vertices until it is satisfied.

All that remains is to construct a graph $G$ with chromatic number 5 and no induced $K_5$. Here is a paper that constructs such a graph with 11 vertices at the start of section 2: https://doi.org/10.1002/jgt.3190190111 (note that they construct one that does not contain an induced $K_4$, which is stronger). There is probably a simpler construction for such a graph $G$, but this certainly works.