Interview Cake Graph coloring is when you assign colors to the nodes in a graph.
A legal coloring means no adjacent nodes have the same color:
The color could be used literally. Say we're coloring a map. We'll want to color adjacent states or countries differently so their borders are clear.
The color could also represent some concept or property. For example, say we have a graph where nodes represent university classes and edges connect classes with overlapping students. We could use colors to represent the scheduled class exam time. In an illegal coloring, a student could be booked for multiple exams at once!
Edge coloring is less common, but it's also a thing. A legal edge coloring means no nodes have two edges with the same color.
Interview coming up?
Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.
No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.
No spam. One-click unsubscribe whenever.
You're in! Head over to your email inbox right now to read day one!
