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