graph colouring - OpenGenus IQ: Learn Computer Science

Overview of Graph Colouring Algorithms

In this introductory article on Graph Colouring, we explore topics such as vertex colouring, edge colouring, face colouring, chromatic number, k colouring, loop, edge, chromatic polynomial, total colouring and various algorithmic techniques for graph colouring.

Algorithms

Bipartite checking using Graph Colouring and Breadth First Search (BFS) [O(V+E) time]

The algorithm to determine whether a graph is bipartite or not uses the concept of graph colouring and BFS and finds it in O(V+E) time complexity on using an adjacency list and O(V^2) on using adjacency matrix. It is used to decode codewords and model situations in cloud computing and big data

Algorithms

Graph Coloring Greedy Algorithm [O(V^2 + E) time complexity]

In this article, we have explored the greedy algorithm for graph colouring. graph coloring is a special case of graph labeling ; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints.

Algorithms

Wigderson Graph Colouring Algorithm in O(N+M) time

Wigderson Algorithm is a graph colouring algorithm to color any n-vertex 3-colorable graph with O(√n) colors, and more generally to color any k-colorable graph. In this article, we have explored this wonderful graph colouring article in depth.

Algorithms

Welsh Powell Algorithm for graph coloring in O(N^2) time

Welsh Powell algorithm is used to implement graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints