Prove that in fact ch() = 3. Hint: Use a case distinction according to whether or not two color lists for vertices in the same part of the bipartition have a color in common. By a result of [ErRT80], there are bipartite graphs with an arbitrarily large choosability; thus k-choosability can indeed be a much stronger requirement than k-colorability. This makes Thomassen’s generalization of the five color theorem to list colorings even more remarkable.
Our customer support team is here to answer your questions. Ask us anything!
👋 How can we help with you?