Coloring of undirected graph

Question

Given an undirected Graph with e number of edges and colour value m. So, that we have to check whether the graph can be coloured with m different colours with the condition that no two adjacent vertices are in the same colour.

I have a thought that, for each vertex, if the degree of the vertex < m, then we can colour the graph with m colours.

If for any vertex, the degree is >= m, then we cannot colour the graph with m colours.

I used the above approach and tried to solve M-Colouring graph, it didn't worked.

Can someone tell me, why the above approach is not working?

I had a doubt with one of the test cases that given m = 3, number of vertices = 4, Edges = e where edges are 4->3, 4->2, 1->4, 3->2, 1->2.

It is saying that with 3 colours we can colour the above undirected graph. How can it be possible? The degree of vertex 4 is 3, So, the number of adjacent vertices are 3. If I include the vertex 4 itself, there are four adjacent vertices. How can we colour these four adjacent vertices with only 3 colours? I think it is impossible. If I'm thinking in the wrong way please let me know.

If anything is wrong with the question or with the way of asking a question please comment below, it would be helpful.

Answer 1

From the post of https://stackoverflow.com/a/63760170/14194633 I got to know that the degree of a vertex, doesn't have to do anything with the graph colouring. Because, in colouring, we have to colour in a way such that no two adjacent vertices have the same colour.

From the example which I was posted in the question, given m = 3. The degree of vertex 4 is 3, in my approach I thought, since the degree of vertex 4 is 3, if I include vertex 4 itself, so we have to colour these four vertices which are adjacent to each other and I thought it is impossible to colour four vertices with only m i.e, 3 colors. But it is not true.

Even though the degree of vertex 4 >= m (given m = 3) we can still colour the graph with 3 colours.

The thing here is not to check the degree of the vertex, but to apply the colour to the vertex and check whether its adjacent vertices have the same colour or not

Answer 2

Two neighbors of a node can have the same color, e.g., the graph

1----2
|    |
|    |
4----3

is 2-colorable because we can color the odd vertices with color 1 and the even vertices with color 2. For each vertex v, the neighbors of v have the same color, which is different from v's color, so there is no violation.