Graph Coloring (Practice Interview Question)

You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

You're in!

Given an undirected graph ↴ with maximum degree ↴ $D$ , find a graph coloring ↴

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.

using at most $D+1$ colors.

For example:

First described by Robert Frucht in 1939, the Frucht graph is a 3-regular graph with 12 vertices, 18 edges, and no nontrivial symmetries.

This graph's maximum degree ( $D$ ) is 3, so we have 4 colors ( $D+1$ ). Here's one possible coloring:

Graphs are represented by an array of $N$ node objects, each with a label, a set of neighbors, and a color:

  require 'set'

class GraphNode
  attr_accessor :label, :neighbors, :color

  def initialize(label)
    @label = label
    @neighbors = Set.new
    @color = nil
  end
end

a = GraphNode.new("a")
b = GraphNode.new("b")
c = GraphNode.new("c")

a.neighbors << b
b.neighbors << a
b.neighbors << c
c.neighbors << b

graph = [a, b, c]

Gotchas

$D+1$ colors is always enough. Does your method ever need more colors than that?

Does your method go through every color for every node? You can do better. You don't want $N*D$ in your final runtime.

We can color a graph in linear ↴ time and space (on the number of nodes, edges and/or the maximum degree).

What if the input graph has a loop ↴ ? Does your method handle that reasonably?

Breakdown

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Complexity

$O(N+M)$ time where $N$ is the number of nodes and $M$ is the number of edges.

The runtime might not look linear ↴ because we have outer and inner loops. The trick is to look at each step and think of things in terms of the total number of edges ( $M$ ) wherever we can:

We check if each node appears in its own set of neighbors. Checking if something is in a set is $O(1)$ , so doing it for all $N$ nodes is $O(N)$ .
When we get the illegal colors for each node, we iterate through that node's neighbors. So in total, we cross each of the graphs $M$ edges twice: once for the node on either end of each edge. $O(M)$ time.
When we assign a color to each node, we're careful to stop checking colors as soon as we find one that works. In the worst case, we'll have to check one more color than the total number of neighbors. Again, each edge in the graph adds two neighbors—one for the node on either end—so there are $2*M$ neighbors. So, in total, we'll have to try $O(N+M)$ colors.

Putting all the steps together, our complexity is $O(N+M)$ .

What about space complexity? The only thing we're storing is the illegal_colors set. In the worst case, all the neighbors of a node with the maximum degree ( $D$ ) have different colors, so our set takes up $O(D)$ space.

Bonus

Our solution runs in $O(N+M)$ time but takes $O(D)$ space. Can we get down to $O(1)$ space?
Our solution finds a legal coloring, but there are usually many legal colorings. What if we wanted to optimize a coloring to use as few colors as possible?

The lowest number of colors we can use to legally color a graph is called the chromatic number.

There's no known polynomial time solution for finding a graph’s chromatic number. It might be impossible, or maybe we just haven’t figured out a solution yet.

We can't even determine in polynomial time if a graph can be colored using a given $k$ colors. Even if $k$ is as low as 3.

We care about polynomial time solutions ( $n$ raised to a constant power, like $O(n^2)$ ) because for large $n$ s, polynomial time algorithms are more practical to actually use than higher runtimes like exponential time (a constant raised to the power of $n$ , like $O(2^n)$ ). Computer scientists usually call algorithms with polynomial time solutions feasible, and problems with worse runtimes intractable.

The problem of determining if a graph can be colored with $k$ colors is in the class of problems called NP (nondeterministic polynomial time). This means that in polynomial time, we can verify a solution is correct but we can’t come up with a solution. In this case, if we have a graph that's already colored with $k$ colors we verify the coloring uses $k$ colors and is legal, but we can't take a graph and a number $k$ and determine if the graph can be colored with $k$ colors.

If you can find a solution or prove a solution doesn't exist, you'll win a $1,000,000 Millennium Problem Prize.

For coloring a graph using as few colors as possible, we don’t have a feasible solution. For real-world problems, we'd often need to check so many possibilities that we’ll never be able to use brute-force no matter how advanced our computers become.

One way to reliably reduce the number of colors we use is to use the greedy algorithm but carefully order the nodes. For example, we can prioritize nodes based on their degree, the number of colored neighbors they have, or the number of uniquely colored neighbors they have.

What We Learned

Start your free trial!

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

Show answer

I have an answer Tell me more

Ready for more?

Check out our full course

You only have 3 free questions left (including this one).

Gotchas

Breakdown

Start your free trial!

Solution

Start your free trial!

Complexity

Bonus

What We Learned

Start your free trial!

Ready for more?

Programming interview questions by company:

Programming interview questions by topic: