Graph coloring was initially introduced to find bipartite graphs. What else can i be used to find?
Note: this is actually a difficult topic, best mastered by practice. You should start learning form Greedy Algorithm
Chromatic Number
the least number of colors needed to have no colors ‘touching’
Four Color Theorem
The chromatic number of a planar graph is no greater than four.
Applications:
Scheduling final exams:
How can the final exams at a university be scheduled so no student has two exams at the same time?
Vertex = Courses Edge = At least one common student.
Greedy Coloring Algorithm
Just pick a random vertex, assign it a color, then assign everything its connected to a new color. Then assign their connections preferably a used color, but it can also be new.
this note was imported from my other vault, ideas are not complete :(