UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 10.3 Free with a free account
Graph Coloring and Traversal
Discrete Mathematics · Chapter 10: Graph Theory: Hamiltonian Circuits, Coloring, and RepresentationsSection 10.3 · lesson 69 of 8712 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Discrete Mathematics.
Lesson complete
Earn the 4 college credits for Discrete Mathematics
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Adjacency Matrix and List Representations →← Weighted Graphs and the Traveling Salesman ProblemNext lesson: Adjacency Matrix and List Representations →
In this lesson
Exam slots, map colors and radio channels - one problem.
- Model conflicts with a conflict graph
- Find a chromatic number with 2 bounds
- Trace greedy coloring and its order effects
- State the Four Color Theorem
Transcript
Everything said in the video, section by section (1,822 words). Read along, or search it.
Graph Theory: Hamiltonian Circuits, Coloring, and Representations
Graph Coloring and Traversal
This section turns to a different kind of graph problem: coloring. Exam schedules, map colors and radio channels all turn out to be the same question. How few labels does a graph need, if no edge may join two vertices with the same label?
The Opening Problem
Scheduling Final Exams
Every registrar's office running a final exam period faces the same puzzle. Two exams can't be in the same time slot if even one student is enrolled in both courses. With hundreds of sections and thousands of overlapping enrollments, the scheduling system must give every exam a slot, so that no student ever faces two exams at once. And it should use as few slots as possible, so the exam period doesn't stretch on for weeks. Stripped of the paperwork, it's a graph problem. Make a vertex for every exam. Draw an edge whenever a student takes both exams. Then give each vertex a slot, so that no edge joins two vertices in the same slot. How few slots, or labels, or channels, or colors, are truly needed? That's graph coloring.
10.3.1
Proper Colorings and the Chromatic Number
A conflict graph represents each item that needs a label as a vertex, and joins two items with an edge exactly when they can't share a label. A proper vertex coloring assigns each vertex one of the colors one through k, so that the two ends of every edge get different colors. The colors might really be time slots, map colors or radio channels. The chromatic number of G, written chi of G, is the smallest k for which a proper coloring exists. Pinning down the chromatic number takes two separate arguments. A lower bound shows that fewer colors can't possibly work. An upper bound exhibits a coloring that achieves the number. The most direct lower bound comes from a clique, a set of vertices that are all adjacent to one another. If G has a clique of size k, those k vertices are mutual neighbors, so they need k different colors. So chi of G is at least k.
Worked Example
5 Courses, 6 Conflicts
Here are five courses: C S two oh one, Math two thirty, Bio one ten, Art one fifty, and History two oh five. Call them A through E. Enrollment records show conflicts along exactly six pairs: A B, A C, B C, B E, C D and D E. Lower bound first. A, B and C are pairwise adjacent. That's a clique of size three, so chi of G is at least three. Now the upper bound. Color the triangle A one, B two, C three. D is adjacent only to C and E, so it can take color one. E is adjacent to B, color two, and D, color one, so E takes color three. Check every edge, and each joins two different colors. So three colors work. Three colors are necessary, by the clique, and sufficient, by the coloring. So chi of G is exactly three. In scheduling terms, these five exams need three time slots, and three are enough.
10.3.2
Greedy Coloring
Finding the chromatic number exactly means proving both bounds, which becomes impractical for large graphs. So most systems use greedy coloring instead. Here, traversal just means the order in which the algorithm visits the vertices. It has nothing to do with Euler or Hamiltonian routes. Greedy coloring processes the vertices in a fixed order. Each vertex gets the smallest positive color not already used by one of its earlier colored neighbors. On the five-course graph, in the order A through E: A has no colored neighbors, so it gets one. B's neighbor A has one, so B gets two. C sees one and two, so it gets three. D sees only C's three, since E isn't colored yet, so D gets one. And E sees one and two, from D and B, so it gets three. Three colors, matching chi of G. Greedy happened to find the optimum here. But just like nearest neighbor in section ten point two, that's not guaranteed.
Figure 2
Order Changes the Answer
The order you feed greedy coloring can change how many colors it uses. Take a chain of four courses, W, X, Y, Z, where only consecutive courses conflict. The chain is bipartite. W and Y on one side, X and Z on the other, and every edge crosses between them. So chi of G is two. In the natural order, W gets one, X gets two, Y gets one, and Z gets two. Two colors, optimal. Now color both ends before the middle: W, X, Z, then Y. W gets one, and X gets two. Z gets one, since its only neighbor, Y, isn't colored yet. When Y finally comes up, its neighbors already hold one and two. So Y is forced to color three. Same graph, three colors instead of two. That's fifty percent more, caused entirely by the traversal order.
Cost and a Guarantee
Fast, With a Guaranteed Ceiling
Greedy coloring is fast. With adjacency lists, it visits each vertex once and scans its neighbors once. That's order n plus m, linear in the size of the graph. It also comes with a guarantee. Let delta of G be the maximum degree. When a vertex v is processed, at most its degree's worth of neighbors are already colored, and that's at most delta. Each rules out at most one color. So at most delta colors are excluded, and some color from one to delta plus one is always free. Greedy never uses more than delta plus one colors. That bound can be tight. The chain has maximum degree two, and the bad order used exactly three colors.
Listing 1
Greedy Coloring in Python
Here's greedy coloring in Python. For each vertex in the given order, it collects the colors already used by its neighbors. Then it counts up from one until it finds a color not in that set. On the five-course graph, in the order A through E, it returns A one, B two, C three, D one, E three, matching the trace. And on the chain, in the order W, X, Z, Y, it returns three colors, with Y forced to three. The order is an explicit input, precisely because it changes the result.
10.3.3
Planar Graphs and the Four Color Theorem
Some graphs come from geographic maps. Each region is a vertex, and an edge joins two regions that share a border. Such graphs are planar. A graph is planar if it can be drawn in the plane so that no two edges cross, except where they share an endpoint. Map graphs are always planar, since the regions themselves never cross on the map. And that structural fact makes the Four Color Theorem possible. Every planar graph has chromatic number at most four. Equivalently, any map in the plane can be colored with at most four colors, so that bordering regions differ. We'll state it without proof. It was first proved in nineteen seventy-six by Kenneth Appel and Wolfgang Haken. They reduced the infinitely many planar graphs to about one thousand nine hundred thirty-six configurations, and checked each by computer. It was the first major theorem whose proof depended on computer verification. In nineteen ninety-seven, Robertson, Sanders, Seymour and Thomas gave a simpler proof, with the same strategy, but only six hundred thirty-three configurations. No proof that avoids computer checking has been found.
Worked Example
A Map That Needs All 4
Four colors aren't just enough. Sometimes they're needed. Picture a central county, M, with three counties, N, E and S, arranged around it. Each borders M, and both of its neighbors in the ring. A fifth county, P, borders only N and E. Lower bound. M borders all three outer counties, and the outer three border one another. So M, N, E and S are pairwise adjacent, a clique of size four. Chi of G is at least four. Upper bound. Color M one, N two, E three, and S four. P borders only N and E, so it can reuse color one, M's color, since P and M don't share a border. So this map needs exactly four colors. But notice what the theorem doesn't say. It doesn't claim every planar graph needs four colors, only that four always suffice. Many planar graphs, like the four-course chain, need just two or three.
10.3.4
One Problem, 3 Vocabularies
Exam scheduling, map coloring and frequency assignment are the same problem in different vocabulary. In exam scheduling, a vertex is a course's final exam, an edge means the exams share a student, and a color is a time slot. In map coloring, a vertex is a region, an edge is a shared border, and a color is a map color, capped at four by the theorem. In frequency assignment, a vertex is a radio tower, an edge means two towers are close enough to interfere, and a color is a channel. Compilers use the same idea for register allocation. Each variable is a vertex, and two variables that need to be stored at the same time share an edge.
Worked Example
5 Towers in a Ring
Suppose five radio towers sit on a circular route, and each interferes only with its two neighbors. The interference graph is a five-cycle. Two channels aren't enough. With only two, each edge forces the next tower to switch. So tower one gets one, then two, one, two, and tower five gets one. But towers five and one are adjacent, and now they match. That's a contradiction. And the same argument works for any cycle with an odd number of vertices. Three channels are enough. Use one, two, one, two, and give tower five channel three. Every edge checks out. So chi is three, and that holds for every odd cycle. Real systems face one more complication. Computing the chromatic number exactly is N P hard for general graphs. So large systems run greedy coloring, often many times with different orders, keeping the best result. That's the same spirit as nearest neighbor for the traveling salesman. As for the registrar's five courses, chi is three. So three exam slots are necessary and sufficient, and the greedy trace shows one way to assign them.
Takeaways
Color Wisely
To summarize. A proper coloring never gives adjacent vertices the same color. The chromatic number is found by pairing a clique lower bound with an explicit coloring. Greedy coloring runs in order n plus m time, and never uses more than delta plus one colors. But it isn't guaranteed to reach the chromatic number, and its result depends on the order. The Four Color Theorem says every planar graph needs at most four colors. It was proved by Appel and Haken in nineteen seventy-six, and again in nineteen ninety-seven, both times with computer help. And exam scheduling, map coloring and frequency assignment are one problem, in different vocabulary. Here's something to think about. Map graphs never need more than four colors. But a university's full conflict graph could plausibly need dozens. Both are colored under the same rule. So what property does a map's graph have, by coming from regions drawn in the plane, that an enrollment graph generally lacks? And why does that property cap one graph's chromatic number, but not the other's?
About Discrete Mathematics at UPI Study
Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus Every course with PRO →
Why take it here
Why students take Discrete Mathematics with UPI Study
Where the credit goes
Universities that work with NCCRS
Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Graph Coloring and Traversal
How do you find the chromatic number of a graph?
How does a conflict graph model scheduling final exams?
How does greedy graph coloring work, and why does the vertex order matter?
What does the Four Color Theorem say, and does every planar graph need four colors?
About the Discrete Mathematics course
How many college credits is Discrete Mathematics?
How much does Discrete Mathematics cost and what is included?
Which universities accept UPI Study credits?
How long does Discrete Mathematics take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 4 credits in Discrete Mathematics.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
4 credits · NCCRSEnroll →