Graph coloring studies how to assign colors to vertices so that adjacent vertices receive different colors. This cheat sheet helps students recognize common graph coloring patterns, compute chromatic numbers, and justify coloring arguments. It is useful for discrete mathematics, combinatorics, algorithms, scheduling, and map-coloring problems.
The central idea is the chromatic number , which is the minimum number of colors needed for a proper vertex coloring of a graph . Important tools include lower bounds from cliques, upper bounds from maximum degree, and exact formulas for common graphs. Students should learn both how to construct a valid coloring and how to prove that fewer colors cannot work.
Key Facts
- A proper vertex coloring assigns colors so that if , then .
- The chromatic number is the smallest integer such that has a proper -coloring.
- For a complete graph , every pair of vertices is adjacent, so .
- For a path graph with , the chromatic number is .
- For a cycle graph , when is even and when is odd.
- If is the size of the largest clique in , then .
- For any graph with maximum degree , the greedy coloring method gives the upper bound .
- A graph is bipartite if and only if it has no odd cycle, and every nonempty bipartite graph satisfies unless it has no edges.
Vocabulary
- Graph
- A graph is a structure made of vertices and edges connecting pairs of vertices.
- Proper coloring
- A proper coloring is an assignment of colors to vertices where adjacent vertices always receive different colors.
- Chromatic number
- The chromatic number is the minimum number of colors needed for a proper coloring of graph .
- Clique
- A clique is a set of vertices in which every pair of distinct vertices is connected by an edge.
- Maximum degree
- The maximum degree is the largest number of edges incident to any single vertex in .
- Bipartite graph
- A bipartite graph is a graph whose vertices can be split into two sets so that every edge connects vertices in different sets.
Common Mistakes to Avoid
- Using the number of colors from one coloring as the chromatic number is wrong because requires the minimum possible number of colors.
- Forgetting to prove a lower bound is wrong because showing a valid -coloring only proves , not .
- Coloring adjacent vertices the same color is wrong because a proper coloring requires whenever .
- Assuming every cycle needs three colors is wrong because even cycles satisfy while odd cycles satisfy .
- Confusing clique size with degree is wrong because counts mutually adjacent vertices, while counts edges incident to one vertex.
Practice Questions
- 1 Find and explain why fewer colors cannot work.
- 2 Find and .
- 3 A graph has maximum degree . What upper bound for comes from greedy coloring?
- 4 A graph contains a triangle but also has many extra vertices. What can you conclude about , and why does the triangle matter?
Understanding Graph Coloring & Chromatic Number Reference
A useful way to think about a coloring is as a partition of the vertices into groups. Every vertex in one group receives the same color. No two vertices within that group may be connected by an edge.
Such a group is called an independent set. Therefore, finding a coloring means splitting the graph into as few independent sets as possible. This viewpoint explains why the shape of the graph matters more than the names or positions of its vertices.
A messy drawing can represent a simple coloring problem, while a neat drawing can hide important conflicts. Redrawing a graph without changing which vertices are connected is often a smart first step.
Greedy coloring gives a practical method for building a coloring. Choose an order for the vertices. At each vertex, use the first color not already used by its colored neighbors.
The method always produces a valid result, but it does not always use the smallest possible number of colors. The order can make a major difference. If a highly connected vertex is colored early, later choices may be easier.
If it is colored late, its neighbors may already use several different colors. Students should treat a greedy result as an upper limit unless they can prove it is optimal. Trying two or three different vertex orders is a quick way to see this effect.
To prove an exact chromatic number, combine a construction with a restriction. First, show a coloring that uses a certain number of colors. This proves that no more than that number is needed.
Next, show why fewer colors fail. A set of mutually adjacent vertices gives a direct restriction because every vertex in that set needs its own color. Odd cycles give another important restriction.
Walking around an odd cycle forces colors to alternate, but the final vertex then conflicts with the starting vertex. Notice that a graph can have no triangle and still need three colors.
An odd cycle of length five is the simplest example. Matching a lower bound and an upper bound is the clearest form of a complete proof.
Coloring models conflict situations. In a school timetable, vertices can represent exams and an edge can mean that some students take both exams. Colors then represent time slots.
In a map, regions that share a boundary segment can be connected, while touching at one corner usually does not count as a conflict. The model must be defined carefully before any coloring begins. For disconnected graphs, color each separate component and use the largest number required by any one component.
Isolated vertices never force an extra color because they have no conflicts. Common mistakes include counting crossing lines as vertices, treating color names as meaningful, and assuming that a large degree automatically gives the exact answer. Careful sketches, a stated vertex order, and a short argument for both bounds make solutions much more reliable.