Эрдёш, Рубин и Тэйлор всё в той же работе предположили, что для такой постановки правильным ответом будет не k=4, а k=5. И это и впрямь оказалось так!
В 1993 году Margit Voigt построила пример плоского графа с 238 вершинами, которым сопоставлены списки из 4 цветов так, что сделать правильную раскраску невозможно. И это, несмотря на большое количество вершин, вполне обозримая конструкция: несколько относительно небольших графов, которые вклеиваются в оставленные для них места на следующих этапах конструкции. Собственно — вся статья это всего 5 страниц!
И почти одновременно Carsten Thomassen доказывает, что 5 цветов от каждой страны достаточно. Собственно, его заметка 1994 года (всего на полторы страницы!) называется «Every planar graph is 5-choosable», и её аннотация говорит сама за себя:
We prove the statement of the title, which was conjectured in 1975 by V. G. Vizing and, independently, in 1979 by P. Erdös, A. L. Rubin, and H. Taylor.
А ещё — несколько лет спустя, в 1996 году пример плоского графа с меньшим числом вершин (всего 63) и сопоставления 4-элементных множеств цветов его вершинам, из которого нельзя выбрать правильную раскраску, построила будущая филдсовская медалистка, а тогда ещё только студентка Мариам Мирзахани (совсем незадолго до того, в 1994 и 1995 годах, выигравшая золото на IMO). И он совсем обозримый — умещается на страницу (см. картинку). Более того, этот же пример несложно правильно раскрасить в 3 цвета — так что из него следует и отрицательный ответ на вопрос «А вот если плоский граф можно раскрасить в 3 цвета, будет ли он обязательно 4-выбираемым?».
References:
[1] M. Voigt, List colourings of planar graphs, Discrete Mathematics
120 (1993), pp. 215-219.
[2] C. Thomassen, Every Planar Graph Is 5-Choosable, Journal of Combinatorial Theory, Series B, 62:1 (1994), pp. 180-181.
[3] Mirzakhani, Maryam. A small non-4-choosable planar graph. Bull. Inst. Combin. Appl., 17 (1996), pp. 15-18.