A bipartite graph K_{3,3} has chromatic number 2. Someone claims: 'We have 6 different colors available — one assigned to each vertex — so we can always list-color it.' The lists each have size 1. What is wrong with this reasoning?
AK_{3,3} actually requires 3 colors, so the chromatic number assumption is wrong
BList coloring requires every vertex's list to have size k; with size-1 lists, adjacent vertices may receive the same color, making a valid coloring impossible
CHaving 6 distinct colors for 6 vertices guarantees a valid coloring regardless of adjacency
DBipartite graphs are not list-colorable because they contain no odd cycles
The error is confusing 'many total colors available' with 'lists large enough to guarantee a valid coloring.' In list coloring, each vertex must be colored from its own private list. If adjacent vertices are forced to share the same color because their size-1 lists happen to contain the same color, no valid coloring exists regardless of how many distinct colors are used globally. The adversary chooses the lists to maximize conflict — a carefully designed size-1 list assignment for K_{3,3} can make coloring impossible.
Question 2 Multiple Choice
Which statement correctly describes the relationship between the chromatic number χ(G) and the list chromatic number χ_ℓ(G)?
Aχ(G) = χ_ℓ(G) always, because the adversary can never do worse than the uniform case
Bχ_ℓ(G) ≤ χ(G) always, because list coloring is strictly more flexible
Cχ(G) ≤ χ_ℓ(G) always, and the gap can be dramatic — for example, K_{n,n} has χ = 2 but χ_ℓ = Θ(log n)
Dχ_ℓ(G) < χ(G) for all graphs with at least one cycle
Because the uniform case (all lists identical) is a special case of list coloring, any graph that requires k colors in standard coloring will also require at least k colors in list coloring. So χ(G) ≤ χ_ℓ(G) always. The gap can be large: K_{n,n} has chromatic number 2 (it's bipartite) but list chromatic number Θ(log n), because an adversary can construct list assignments that defeat any fixed coloring strategy for small list sizes.
Question 3 True / False
If a graph can be properly colored with k colors, it can usually be properly list-colored from any assignment of lists of size k.
TTrue
FFalse
Answer: False
This is the central misconception list coloring is designed to expose. Standard k-colorability means there exists *one* assignment of k colors that works when all vertices draw from the same pool. List k-choosability (χ_ℓ ≤ k) means the graph can be colored *no matter what* specific k colors each vertex's list contains. These are very different guarantees. K_{n,n} is 2-colorable but not 2-choosable — a cleverly designed list assignment of size 2 can make it impossible to color.
Question 4 True / False
The list chromatic number of a graph is always at least as large as its standard chromatic number.
TTrue
FFalse
Answer: True
When all vertex lists are identical (each list = the same set of k colors), list coloring reduces exactly to standard k-coloring. So if the graph can be list-colored from any k-size lists, it can certainly be colored from k colors in the standard sense. Contraposing: if standard k-coloring fails, list k-coloring fails too. Therefore χ(G) ≤ χ_ℓ(G) always holds.
Question 5 Short Answer
Why does having many total colors available across all vertex lists not guarantee that a graph can be list-colored from those lists?
Think about your answer, then reveal below.
Model answer: In list coloring, the adversary chooses which specific colors go on each vertex's list, and they choose adversarially to make coloring as hard as possible. Even if the total pool of colors is vast, a clever adversary can assign lists so that every possible color assignment to one vertex conflicts with every neighbor's available colors. The guarantee in k-choosability is not about the number of colors globally — it's about being able to succeed against *any* assignment of size-k lists, including the worst-case adversarial one.
This is the core insight that separates list coloring from standard coloring. Standard coloring gives you full control over the color assignment; list coloring hands partial control to an adversary. The adversary exploits the graph's structure to design list assignments that force conflicts. This is why K_{n,n}'s list chromatic number grows with n even though its standard chromatic number is always 2.