Coloring of undirected graph
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 withmcolours.
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.
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
- Is it possible to divide points to regions only based on their minimum distance to region-dividing curves?
- How can I find a number in a list (smaller than a given bound but the biggest one)?
- Balanced Partition greedy approach
- Algorithm for minimizing (s[i]-s[j]+d)/(i-j)
- Find longest substring
- Fish codility excercise
- Next prime number algorithm
- Using Loop invariant to prove correctness of merge sort (Initialization , Maintenance , Termination)
- Allocate bikes to people - First Priority (Closest bike to closest person)
- Isolation Forest Sklearn for 1D array or list and how to tune hyper parameters
- If the n-body problem is chaotic, why isn't it used as a RNG?
- Implementing Miller-Rabin in C
- Prove or disprove: there exists three vertexes a,b,c in a connected but incomplete graph satisfying a and b have a common neighbor c
- Boolean formula for a graph vertex-colouring algorithm
- heapq with custom compare predicate
- Algorithm to calculate number of intersecting discs
- Verifying the minimum cost from each node to a sink node in linear time
- Variations with repetition of r integers in {0...k} that sum to u
- How to reconstrunct a binary tree from an array produced by preorder tree traversal
- Two implementation methods of BFS for finding the shortest path, which one is the obvious winner?
- Determining coefficient of x^m term in (x^2 + x + 1)^n is even or odd
- How to merge 3 sorted arrays into 1 sorted array in Big-O(N) time?
- what is the best algorithm for this game?
- codility absolute distinct count from an array
- Avoid duplicates in N Queen iterative solutions (No Recursion Allowed)
- Split a binary search Tree
- minimum number of steps to reduce number to 1
- How to fix 'Codility FrogJump' Algorithm?
- Suffix tree VS Tries - in plain English , what's the difference?
- Pollard Rho factorization method implementation