The Two Coloring Graph Problem

Question

Given a graph, can you use two colors to color each node of the graph, such that no two adjacent nodes have the same color?

The Problem

The graph coloring problem is a well-known problem in computer science. It requires coloring different nodes of the graph so that two adjacent nodes do not have the same color.

In this challenge, we'll look at a special case of this problem, where we'll determine if two colors suffice for graph coloring or not. The 2 coloring problem is also equivalent to creating a partition of a set of elements, so that two connected elements are in two different partitions.

The Basic Idea for a Solution

To implement a solution to the 2 coloring problem, we need to visit each node of the graph, which can be done via a depth-first or breadth-first traversal. Initially, none of the nodes is colored so we can assign an arbitrary color to the first node. Once the traversal begins, we check two cases for a node n:

• One or more adjacent nodes of n have been assigned the same color. n can be assigned the opposite color.
• Two or more adjacent nodes of n have been assigned opposite colors. It is not possible to assign n a valid color.

These two cases are shown in the figure below. The gray node has to be assigned a color.

Pseudo-code:

To implement the 2-coloring problem, we'll use the breadth-first search strategy to visit and process each node. A queue is required for the implementing breadth-first search. For this problem, every node requires three attributes. One attribute is the color attribute, which is assigned to the node. As this is a two coloring problem, we'll make color a boolean variable called red, which would be true if the color of the node is red, otherwise false. The three attributes for each node are:

• assigned: Initially it is set to false and set to true once a color is assigned to the node.
• red: True if the color of the node is red, otherwise false.
• added: Initially false. Set to true once the node is added to the queue.

The pseudo-code for the solution is:

Routine: twoColoringProblem
Input: A graph
Output: True if 2 coloring is possible, false otherwise.

1. Initialize the attributes assigned,red and added of each node to false.
2. Add the first node to the queue
3. noClash = true
4. while (queue is not empty and noClash)
	a. Remove a node n from the queue
	b. get all adjacent nodes of n which have been assigned a color
			if all have the same color then
				assign the opposite color to n
				set the assign attribute of n to true
			else
				noClash = false
	c. get all adjacent nodes of n which have not been assigned a color
	   and have not been added to the queue
			add all these nodes to queue and set their added attribute to true
5. return noClash

The entire method is shown in the figure below:

Concluding Remarks

The 2 coloring problem requires the processing of each node of the graph. For each node, we have to check its adjacent nodes. Depending upon which data structure is used to implement the graph, the time complexity of the above procedure would vary. If an adjacency list is used, then the time complexity is O(nk), where k is the maximum degree of all nodes of the graph. For an adjacency matrix, the time complexity would be O(n^2).

One Pager Cheat Sheet

• The Graph Coloring Problem can be solved by partitioning the elements into two different sets such that no two adjacent nodes have the same color.
• A graph can be successfully 2-colored by visiting each node and assigning an arbitrary color to the first node, then assigning the opposite color to a node n for any of its adjacent nodes that have already been assigned the same color, or determining that it cannot be validly colored if two or more of its adjacent nodes already have opposite colors.
• The 2-coloring problem can be solved using breadth-first search with each node being assigned the attributes assigned, red and added.
• The entire method is illustrated in the figure below.
• Executing the 2 coloring problem on an adjacency matrix has a time complexity of O(n^2), whereas an adjacency list would have a time complexity of O(nk) where k is the maximum degree of all nodes in the graph.