1
$\begingroup$

If a graph is 4-list-colorable, then it is easy to see that it has exponentially many 5-list colorings. This is the first sentence in [Exponentially many 5-list-colorings of planar graphs,JCTB,97 (2007) 571–583]

I do not understand why a graph must have exponentially many 5-list colorings when it is 4-choosable.

Could any one explain the sentence above. Thanks

$\endgroup$
6
$\begingroup$

Take $5$-lists at every vertex. There are $5^n$ ways to reduce them to $4$-lists. Each of these ways allows a coloring, so you have $5^n$ pairs of a $4$-list and a coloring.

How many of these colorings can be identical? Given a coloring, $4^n$ of the $4$-lists allow the same coloring, as you are not allowed to delete the particular color from the list. Double counting the pairs, you get that there are at least $\left(\frac54\right)^n$ colorings total.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.