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.
A two-colourable undirected graph.
In this lesson, we will learn more about using graph traversal algorithms to solve the two-colouring problem in an undirected graph, and how to identify a problem as a two-colouring pattern problem.
Equivalence of two-colourable and bipartite graphs
It is important to note that every graph that is two-colourable can be rearranged as a bipartite graph. This is because we can arrange the nodes of the same colour in a set, creating two disjoint sets. Since no two adjacent nodes in a two-colourable graph can have the same colour, in the rearranged graph, there will be no edge between nodes of the same set, making it a bipartite graph.
Every two-colourable graph is a bipartite graph.
Liking the course? Check our discounted plans to continue learning.