All non-isomorphic graphs with chromatic number 4

Question

I need to find all non-isomorphic graphs $G=(V,E), |V|=5$ with chromatic number $\chi(G) = 4$. How do I do that?

Answer 1

HINT: What’s the only graph on $4$ vertices with chromatic number $4$? Start there, and see how you can add a vertex.

Added: I did not mean to imply that this will give you all possible graphs on $5$ vertices with chromatic number $4$, but rather that it gives you a good starting point. However, one can show that in fact any graph $G$ on $5$ vertices with chromatic number $4$ does contain a copy of $K_4$. Start with $G$, and remove one vertex to get a graph $G'$ on $4$ vertices; if $G'$ is a copy of $K_4$, you’re done. If not, show that $G'$ contains a triangle (because otherwise $\chi(G')\le 2$, and $\chi(G)\le 3$). Finally, show that $G$ must contain a copy of $K_4$.

Answer 2

Since $G\ne K_5$ we may assume $\{v_4,v_5\}\notin E$. If, e.g., $\{v_1,v_2\}\notin E$ as well then $G$ could be tricolored according to the partition $\{v_1,v_2\}\cup\{v_3\}\cup\{v_4,v_5\}$. It follows that ($G$ restricted to) $T:=\{v_1,v_2,v_3\}$ is a $K_3$. If both $v_4$ and $v_5$ were connected to at most two vertices of $T$ the graph $G$ again could be tricolored. Therefore we may assume that $v_4$ is connected to all three vertices of $T$, which implies that $Q:=\{v_1,v_2,v_3,v_4\}$ is a $K_4$. Finally the vertex $v_5$ is connected to $0\leq k\leq3$ vertices of $Q$. It follows that there are four isomorphy types, parametrized by $k$.