Assign each vertex a color so that no edge joins two vertices of the same color, using as few colors as the graph will honestly allow. That's the whole idea behind graph coloring, and it turns out to model scheduling conflicts, register allocation in compilers, and radio frequency assignment far more directly than the "coloring a map" framing usually suggests.
Think of each vertex as a person who needs to be assigned a work shift, and each edge as "these two people can't work the same shift because they'd conflict." A proper coloring is any shift assignment that avoids every conflict; the chromatic number is the fewest shifts a manager could possibly get away with, if they're clever about it. Giving everybody their own separate shift always avoids every conflict, so a valid schedule always exists -- the real puzzle is how much the manager can consolidate before some pair of conflicting people ends up sharing a shift anyway. The classic picture is a map: color each country so that no two countries sharing a border get the same color, the way an atlas keeps neighboring nations visually distinct. Three mutually touching countries force three different colors between them, the same way three people who all conflict with each other need three separate shifts.
Graph coloring is the task of assigning each vertex a color so that no two adjacent vertices share a color; a coloring that succeeds at this is called a proper coloring -- edges are exactly the constraints a coloring has to respect, and nothing else about the graph matters to the definition. A graph is always properly colorable using one color per vertex (every vertex gets its own unique color, and no two same-colored vertices are ever adjacent because no two vertices share a color at all), so the real question is never whether a proper coloring exists, but how few colors one can get away with.
The chromatic number of a graph is the fewest colors any proper coloring of it can use. Two easy bounds pin it down before any real work: a graph containing a triangle needs at least 3 colors (any 2-coloring forces two of the triangle's three mutually-adjacent vertices to share a color), and a bipartite graph needs at most 2, since splitting into its two parts is a valid 2-coloring by definition. Finding the exact chromatic number of an arbitrary graph is far harder than checking either bound -- computing it in general is one of this course's own later examples of a problem with no known fast algorithm.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
What is the minimum number of colors for a proper coloring of the cycle C_8?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
C_8 is an even cycle, hence bipartite: alternate two colors around the cycle.
Correct answer
Also accepted:
Why
Check whether C_8's length lets you alternate two colors all the way around without a clash.
From Discrete Mathematics II — Combinatorics
A student colors C_5 alternately with 2 colors and finds the last edge monochromatic. What is the underlying reason?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Odd cycles are the obstruction to 2-colorability; no starting point or ordering rescues 2 colors on C_5. Even cycles alternate fine.
Alternating around an odd-length cycle eventually forces the first and last colors to compare -- work out what happens to that comparison.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
What is the chromatic number of the complete graph K_5?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
All five vertices are mutually adjacent, so all five need distinct colors, and five colors trivially suffice.
Correct answer
Also accepted:
Why
From Discrete Mathematics II — Combinatorics
What is the chromatic number of the wheel W_5 (a 5-cycle plus a hub adjacent to all rim vertices)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The odd rim needs 3 colors, and the hub touches every rim vertex, forcing a 4th; coloring rim with 3 and hub with the 4th works.
Correct answer
Also accepted:
Why
Color the 5-vertex rim first using the fewest colors an odd cycle needs, then see what color is left available for the hub.
Find the fewest colors this graph needs
Try coloring this graph with 2 colors first. If a conflict (red edge) forces you to stop, that's evidence 2 isn't enough -- go back and see how few colors actually work.
Loading interactive…
Worked example
Coloring a graph that contains a triangle
-
1
What is the chromatic number of a triangle -- three vertices, all three pairs joined by an edge?
-
2
Every pair of the triangle's three vertices is adjacent, so any two of them sharing a color is automatically a conflict.
-
3
With only 2 colors, three vertices force at least two of them into the same color by the pigeonhole principle -- and any two of the triangle's vertices being the same color is a violation. Three colors, one per vertex, has no such collision.
-
4\boxed{3}
Loading interactive…
Worked example
Recognizing a graph that needs only 2 colors
-
1
A graph is a single 6-cycle -- six vertices arranged in a loop, each adjacent to its two neighbors. What is its chromatic number?
-
2
Check whether the graph is bipartite first, since a bipartite graph's chromatic number is at most 2 automatically.
-
3
The cycle has even length (6), so the odd-cycle test confirms it's bipartite: alternate the colors around the loop, red-blue-red-blue-red- blue, and the sixth vertex's neighbors (the first and fifth) both land on the opposite color from it.
-
4\boxed{2}
A graph needs at least 2 colors the moment it has even a single edge (the two endpoints can't match), so 2 is also the smallest possible chromatic number any graph with an edge could have -- this cycle hits that floor exactly.
Loading interactive…
Worked example
Diagnosing a broken coloring attempt
-
1
A student colors a 4-vertex graph with edges AB, BC, CD, DA using colors: A= red, B= blue, C= red, D= red. They claim this uses only 2 colors, so the chromatic number is 2. What's wrong?
-
2
Check every edge against the claimed coloring, not just count how many distinct colors got used: CD joins C= red and D= red -- same color, same edge.
-
3
A coloring that violates even one edge isn't a proper coloring at all, regardless of how few colors it uses -- "uses 2 colors" and "is a valid 2-coloring" are different claims.
-
4\boxed{\text{Invalid} - \text{edge } CD \text{ is monochromatic, so this isn't a proper coloring}}
This 4-cycle is in fact 2-colorable (it's bipartite), just not with the particular assignment given -- swapping D to blue fixes the only conflict.
Who uses this
Compilers and scheduling
A compiler assigning a program's variables to a limited set of physical CPU registers builds a conflict graph -- an edge between two variables that are ever "alive" at the same time -- and then colors it: each color is one physical register, and a proper coloring guarantees no two simultaneously-live variables ever collide in the same register. The fewer colors (registers) the compiler needs, the less it has to spill variables to slower memory, which is exactly why register allocation is graph coloring wearing a different name.
Check your understanding (counts toward your progress)
A graph has an isolated vertex v (degree 0) alongside the rest of the graph. What color(s) could v receive in a proper coloring that already colors the rest of the graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A fresh color is never required just because a vertex is isolated.
An isolated vertex still needs a color like any other, and assigning one is trivial precisely because it has no neighbors.
'Nearest' isn't a meaningful constraint here -- only adjacency (sharing an edge) matters, and v has none.
Why
Since v touches no edges, no existing color choice anywhere in the graph can conflict with whatever color v receives -- any color at all works.
Check what colors are actually forbidden for v by asking which vertices are adjacent to it.
What must be true of a proper coloring of a graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That would use one color per vertex -- always valid, but far more colors than usually necessary.
Nothing requires a color to repeat at all.
Color count and edge count aren't tied together this way.
Why
A proper coloring's only requirement is that adjacent vertices never share a color -- nothing else about the assignment is constrained.
A coloring assigns colors \{1,2,1,3\} to vertices A,B,C,D where the graph's edges are AB, BC, CD. Is this a proper coloring?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A and C aren't adjacent here -- the edge list is AB, BC, CD, with no edge AC -- so sharing a color between them isn't a violation.
Check CD's actual colors again: C is color 1, D is color 3 -- different colors, no conflict.
The edge list given is enough information to check every edge directly.
Why
Check each listed edge: AB (colors 1, 2 -- fine), BC (2, 1 -- fine), CD (1, 3 -- fine). A and C share color 1, but no edge joins them, so that's not a conflict -- this coloring is proper.
Check only the pairs of vertices actually joined by a listed edge, and ignore any color repeats between vertices that aren't adjacent.
Vertices A and B are NOT adjacent. Does a proper coloring forbid them from sharing a color?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
That would describe giving every vertex its own unique color -- always valid, but far stricter than the actual rule.
Why
A proper coloring's only constraint is on adjacent pairs -- two non-adjacent vertices sharing a color creates no conflict at all.
Practice: Building a proper coloring (4 problems · doesn’t affect your progress)
A coloring assigns the same color to two vertices joined by an edge. Is it a proper coloring?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The one rule a proper coloring must follow is that no edge's two endpoints share a color.
No -- adjacent vertices sharing a color is exactly what a proper coloring forbids
Does giving every vertex in a graph its own unique color always produce a proper coloring?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
If every vertex has a distinct color, no pair of vertices (adjacent or not) ever shares one, so no edge can possibly be monochromatic.
Yes -- no two vertices share a color, so no edge can be monochromatic
A proper coloring of an 11-vertex graph uses 4 vertices for color 1 and 4 for color 2. How many vertices are left for color 3, if only 3 colors are used total?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every vertex needs exactly one color: 11-4-4=3.
Correct answer
Also accepted:
Why
Subtract the vertices already accounted for by colors 1 and 2 from the total vertex count.
A coloring attempt has exactly one monochromatic edge. Does fixing just that one edge's conflict (by recoloring one of its two endpoints) always produce a valid proper coloring?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Changing one vertex's color can fix the one flagged conflict while accidentally creating a new one against a different neighbor -- fixing a coloring isn't always a purely local, one-edge-at-a-time process.
Think about all the other edges touching the vertex you're about to recolor, not just the one flagged conflict.
Ask whether the new color could create a fresh conflict with one of those other neighbors.
Not necessarily -- recoloring that vertex could create a new conflict with one of its other neighbors
Check your understanding (counts toward your progress)
Graph P has chromatic number 2, and graph Q has chromatic number 4. What can you say about their edge counts?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A sparse graph can still need many colors (a certain structure forces it), and a dense one can sometimes need few -- edge count and chromatic number aren't tightly linked.
Chromatic number 2 only requires bipartiteness -- it doesn't force the graph to be cycle-free.
Chromatic number 4 doesn't require every possible edge to be present.
Why
Chromatic number depends on a graph's adjacency structure, not simply how many edges it has -- a sparse graph can be hard to color and a dense one can sometimes color easily, so edge count alone doesn't determine or get determined by it.
Think of a sparse graph that still needs many colors, and a dense graph that colors easily, to test whether edge count and chromatic number actually move together.
What is the chromatic number of a graph with 4 vertices and no edges at all?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
With no edges, no two vertices are ever adjacent, so one single color satisfies every constraint (there are none to violate).
Correct answer
Also accepted:
Why
A graph is bipartite and has at least one edge. What is its chromatic number?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
At least one edge means its two endpoints can't share a color, so a single color is never enough.
Size doesn't matter here -- the two-part split itself is exactly a valid 2-coloring for any bipartite graph.
Bipartiteness alone is sufficient information: the two-part split is always a valid 2-coloring.
Why
A bipartite graph's own two-part split is automatically a valid 2-coloring, and any graph with an edge needs at least 2 colors -- so a bipartite graph with an edge has chromatic number exactly 2.
Recall what a bipartite graph's own two-part split already gives you for free, and check whether one color alone could survive once an edge exists.
A graph consists of two separate triangles (6 vertices total, no edges between the two triangles). What is its chromatic number?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Each triangle alone needs 3 colors, and since the two triangles share no edges, the very same 3 colors can be reused for the second triangle -- the whole graph still needs (and only needs) 3 colors total.
Correct answer
Also accepted:
Why
Find the chromatic number each triangle needs completely on its own.
Ask whether the two triangles sharing no edges lets the very same set of colors be reused for both.
Practice: Reasoning about the chromatic number (4 problems · doesn’t affect your progress)
What is the chromatic number of a graph with 5 vertices and no edges?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
With no edges, nothing forbids reusing a single color everywhere.
Correct answer
Also accepted:
Why
What is the chromatic number of a single edge (2 vertices, 1 edge)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The two endpoints are adjacent, so they need distinct colors -- 1 color is never enough once any edge exists.
Correct answer
Also accepted:
Why
A graph is bipartite with at least one edge. What is its chromatic number?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A bipartite graph's own two-part split is always a valid 2-coloring, and at least one edge rules out using just 1 color.
A bipartite graph's two-part split doubles as a coloring already -- ask how many colors that split alone uses, and whether one edge could survive with fewer.
2
A graph is made of 4 separate triangles, sharing no vertices or edges. What is its chromatic number?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Each triangle alone forces 3 colors, and since the triangles share nothing, the same 3 colors can be reused across all four -- the whole graph needs (and only needs) 3.
Correct answer
Also accepted:
Why
Work out what one triangle alone requires.
Ask whether the triangles sharing no vertices or edges lets that same requirement be reused instead of stacked up.