2020/06/28 by Xu, Rongxing, Zhu, Xuding
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2006.15614
A graph G is called 3-choice critical if G is not 2-choosable but any proper subgraph is 2-choosable. A characterization of 3-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrift, Tu Ilmenau(1998)]. Voigt conjectured that if G is a bipartite 3-choice critical graph, then G is (4m, 2m)-choosable for every integer m. This conjecture was disproved by Meng, Puleo and Zhu in [On (4, 2)-Choosable Graphs, Journal of Graph Theory 85(2):412-428(2017)]. They showed that if G=Θr,s,t where r,s,t have the same parity and min\r,s,t\ ≥ 3, or G=Θ2,2,2,2p with p ≥ 2, then G is bipartite 3-choice critical, but not (4,2)-choosable. On the other hand, all the other bipartite 3-choice critical graphs are (4,2)-choosable. This paper strengthens the result of Meng, Puleo and Zhu and shows that all the other bipartite 3-choice critical graphs are (4m,2m)-choosable for every integer m.