Minimum number of colors needed to color the graph

Question

What is the chromatic number of the below graph?

I am preparing for a competitive exam, and I am required to solve questions in under 3 minutes.

Well, I first tried to color the graph using basic steps such as not giving any two adjacent vertices the same color. But with this approach, I sometimes end up with the wrong answer.

However, whenever I answer by counting the minimal number of largest maximal independent sets that cover all vertices of the graph, I do get the correct answer, but this approach takes time.

Please suggest a method for such types of problems so that the correct answer can be given in a reasonable amount of time.

Answer 1

This graph is planar so $\leq 4$. But it is doable by $3$ colors.

It is not doable with $2$ colors since we have subgraph $K_3$.

Answer 2

For a more general answer, use $\chi(G) = \min\{\chi(G + uv), \chi(G/uv)\}$ where $u$ and $v$ are non-adjacent vertices and $G/uv$ denotes a contraction of $G$, obtained by identifying the vertices $u$ and $v$. The logic here is that if $u$ and $v$ have the same colour in a minimal colouring, we may as well contract them and this won't affect the minimal number of colours used, and if they have different colours then adding an edge between them won't affect the number of colours used. Since $u$ and $v$ either have the same colour or different colours, we just take the minimum between the two options.

In your case, since the neighbourhood of Ed is contained in the neighbourhood of Def, we should contract Ed and Def (and colour them both red), and similarly we should contract $Fra$ and $Fa$ (and colour them both blue). Continuing in this way, you end up with a complete graph on three vertices, which has chromatic number three.