Understanding the two colouring pattern
Graph colouring is the assignment of labels to elements of a graph where the assignment is subject to certain constraints. Vertex colouring is a subset of graph colouring problems where the nodes of the graph must be coloured such that no two adjacent nodes have the same colour. The two-colouring, as the name suggests, is a vertex colouring problem where we only have two colours, and we need to determine if colours can be assigned to the nodes of the graph such that adjacent nodes have different colours.
In this course, we will only learn about solving the two-colouring problem for an undirected graph. All references to a graph in this lesson mean an undirected graph. Two-colouring a directed graph is a hard problem beyond the scope of this course.
The two colouring pattern is a classification of two-colouring problem on a graph that can be solved using the two-colouring technique.
Liking the course? Check our discounted plans to continue learning.