Graph Coloring
Graph coloring involves assigning colors to elements of a graph such that no adjacent vertices share the same color. It models constraints and optimization problems in scheduling, resource allocation etc.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| int[] graphColoring(int[][] graph) {
int n = graph.length;
int[] colors = new int[n];
for (int i = 0; i < n; i++) {
Set<Integer> assigned = new HashSet<>();
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1 && colors[j] != 0) {
assigned.add(colors[j]);
}
}
int color;
for (color = 1; color <= n; color++) {
if (!assigned.contains(color)) {
break;
}
}
colors[i] = color;
}
return colors;
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| vector<int> graphColoring(vector<vector<int>> graph) {
int n = graph.size();
vector<int> colors(n, 0);
for (int i = 0; i < n; i++) {
unordered_set<int> assigned;
for (int j = 0; j < n; j++) {
if (graph[i][j] && colors[j]) {
assigned.insert(colors[j]);
}
}
int color;
for (color = 1; color <= n; color++) {
if (!assigned.count(color)) {
break;
}
}
colors[i] = color;
}
return colors;
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| def graph_coloring(graph):
n = len(graph)
colors = [0] * n
for i in range(n):
assigned = set()
for j in range(n):
if graph[i][j] and colors[j]:
assigned.add(colors[j])
color = 1
while color in assigned:
color += 1
colors[i] = color
return colors
|
Graph coloring is NP-Hard in general but has many approximate and heuristic algorithms. Useful in resource optimization and scheduling.
Graph coloring is an assignment of labels, or “colors,” to the vertices of a graph in such a way that no two adjacent vertices have the same color. This problem often appears in real-world situations like scheduling and conflict resolution. In simpler terms, imagine you have a map, and you want to color each country so that no two neighboring countries have the same color.
Example Code in Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class GraphColoring {
static boolean isSafe(int[][] graph, int[] colors, int v, int c) {
for (int i = 0; i < graph.length; i++) {
if (graph[v][i] == 1 && colors[i] == c)
return false;
}
return true;
}
static boolean graphColoringUtil(int[][] graph, int m, int[] colors, int v) {
if (v == graph.length)
return true;
for (int c = 1; c <= m; c++) {
if (isSafe(graph, colors, v, c)) {
colors[v] = c;
if (graphColoringUtil(graph, m, colors, v + 1))
return true;
colors[v] = 0;
}
}
return false;
}
public static void main(String[] args) {
int[][] graph = { /* your adjacency matrix here */ };
int m = 3; // Number of colors
int[] colors = new int[graph.length];
if (graphColoringUtil(graph, m, colors, 0))
System.out.println("Solution exists");
else
System.out.println("No solution exists");
}
}
|
Example Code in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include <iostream>
#include <vector>
using namespace std;
bool isSafe(vector<vector<int>> &graph, vector<int> &colors, int v, int c) {
for (int i = 0; i < graph.size(); ++i) {
if (graph[v][i] && colors[i] == c) return false;
}
return true;
}
bool graphColoringUtil(vector<vector<int>> &graph, int m, vector<int> &colors, int v) {
if (v == graph.size()) return true;
for (int c = 1; c <= m; ++c) {
if (isSafe(graph, colors, v, c)) {
colors[v] = c;
if (graphColoringUtil(graph, m, colors, v + 1)) return true;
colors[v] = 0;
}
}
return false;
}
int main() {
vector<vector<int>> graph; // Your adjacency matrix here
int m = 3; // Number of colors
vector<int> colors(graph.size(), 0);
if (graphColoringUtil(graph, m, colors, 0))
cout << "Solution exists";
else
cout << "No solution exists";
}
|
Example Code in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def is_safe(graph, colors, v, c):
for i in range(len(graph)):
if graph[v][i] == 1 and colors[i] == c:
return False
return True
def graph_coloring_util(graph, m, colors, v):
if v == len(graph):
return True
for c in range(1, m + 1):
if is_safe(graph, colors, v, c):
colors[v] = c
if graph_coloring_util(graph, m, colors, v + 1):
return True
colors[v] = 0
return False
graph = [] # Your adjacency matrix here
m = 3 # Number of colors
colors = [0 for _ in range(len(graph))]
if graph_coloring_util(graph, m, colors, 0):
print("Solution exists")
else:
print("No solution exists")
|
We start with the first vertex and try to color it with each color from 1 to m, where m is the number of colors. If a color assignment is valid, we move to the next vertex. We backtrack if we cannot find a solution.
title: Graph Coloring
excerpt: In graph coloring, the goal is to color the vertices in a graph so that no vertices that share an edge have the same color.
tags: graph-coloring
In graph coloring, the goal is to color the vertices in a graph so that no vertices that share an edge have the same color. There are two questions related to graph coloring:
- What is the smallest number of colors you can use to color a given graph?
- What is the smallest number of colors you can use to color any map?
Solution Outline
Pick any vertex and give it one of the two colors. Then give each of its neighbors the other color and recursively visit them to color their neighbors. If you ever come to a point where a node’s neighbor already has the same color as the node, the graph cannot be two-colored.
- Make a queue of nodes that have been colored.
- Color the first node and add it to the queue.
- Traverse the graph, coloring the nodes.
- Dequeue the next node from the colored queue.
- Caculate the node’s neighbor color.
- Color the node’s neighbors
- See if the neighbor is already colored
- Color the neighbor that has not been colored
This assumes that the graph is completely connected. If it is not, use the algorithm repeatedly for each connected component. Read about how to solve [Is Graph Bipartite?]({% post_url 2021-04-27-bipartite-graph %}) problem.