Determine Whether A Given Undirected Graph is Two-Colorable in Python

What does Two-Colorable mean for a graph?

A two-colorable graph is a graph in which each vertex can be assigned a color (out of any two given colors, here we will assume these colors to be BLACK and WHITE) and none of its adjacent vertices have the same color.

The problem that we are going to solve is to check whether a given undirected graph is two-colorable or not.

Examples:

The simplest example of a two-colorable graph is a graph with 2 vertices and a single edge. One of the edges would be colored white and the other would be black.

An example of a graph that is NOT two-colorable is a 3 vertex cycle. In fact, any graph which contains an odd cycle is NOT two-colorable.

How to check a two-colorable graph?

For two coloring a graph, the main point to focus upon is that once we pick a color for a particular vertex, all its adjacent vertices must have the opposite color. So deciding on a color for a particular vertex means that the colors of all its adjacent vertices can’t be decided by us. Also, the choice of color for the first vertex (whether it is white or black) does not matter, as swapping from one to the other will simply change the color of all other vertices.

With this logic in our mind, we can now take the greedy approach. We perform a depth-first search on the graph and check each vertex: if it hasn’t been colored yet, then we choose a color for that vertex and color its adjacent vertices with the opposite color. At any point, if a vertex has any of its adjacent vertices with the same color, then we can recognize the graph being NOT two-colorable.

Pseudocode for the solution

function TWO_COLOUR(G = (V, E))
Set colour[1..n] = null
for each vertex u = 1 to n do
if colour[u] = null then
if DFS(u, BLACK) = False then
return False
return True
end function
// Returns true if the component was successfully coloured
function DFS(u, c)
colour[u] = c
for each vertex v adjacent to u do
if colour[v] = c then // A neighbour has the same colour as us!
return False
else if colour[v] = null and DFS(v, opposite(c)) = False then
return False
return True
end function

NOTE: Here, opposite(c) is a function that returns WHITE or BLACK if c is BLACK or WHITE respectively

Complexity Analysis

k-colorable graph problems all belong to a certain class of problems called NP-complete except when k=0,1,2. This simply means that k-colorable graph problems (other than when k =0,1,2) can not be solved in a polynomial time complexity( i.e. O(n^k)).

Thus, checking for a two-colorable graph is the maximum number of colors (i.e. ‘k’ = 2) for which a polynomial-time algorithm can be given to solve the k-colorable graph problem. In fact, it can be solved with an algorithm of linear time complexity., i.e., O(n) where n is the size of the input graph.

In our solution, the time complexity for the solution is O(V+E) where V = number of vertices and E = number of edges in the graph.

Implementing the Python code

Below is the Python code to determine whether a given undirected graph is two-colorable or not:

def two_colour(adj_list):
    """
    Input: a graph in the form of an adjacency list

    Output: True if the given graph is 2 colorable,
    False if it is not

    Complxity: O(V+E), where V= number of vertices
    and E= number of edges of the input graph
    """
    n = len(adj_list) # number of vertices
    colour_list = [0]*n # 0 represents no colour
    for u in range(n): # iterating through all the vertices
        if colour_list[u] == 0:
            if DFS(u, 'BLACK', colour_list, adj_list) == False:
                return False
    return True


# function for checking whether a vertex
# was successsfully coloured
def DFS(u, c, colour_list, adj_list):
    colour_list[u] = c
    for v in adj_list[u]:
        if colour_list[v] == c:
            return False
        elif colour_list[v] == 0 and DFS(v, opposite(c), colour_list, adj_list) == False:
            return False
    return True


# returns the opposite colour
def opposite(c):
    if c =='BLACK':
        return 'WHITE'
    elif c =='WHITE':
        return 'BLACK'

Example 1:

This is a 3 vertex cycle graph

two_colour([[1,2],[0,2],[0,1]])

Output:

False

Example 2:

This is a simple graph with 4 vertices connected in the following manner:

0–1–2–3

Where 0,1,2,3 represent vertices and — represents an undirected edge.

two_colour([[1],[0,2],[1,3],[2]])