2022/05/19 by Glenn G. Chappell, Chappell, Glenn G.
Computer Science · #05C15 (Primary) 05C10 #05C83 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2205.09856
openalex publication_date 2022/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For positive integers a and b, a graph G is (a:b)-choosable if, for each assignment of lists of a colors to the vertices of G, each vertex can be colored with a set of b colors from its list so that adjacent vertices are colored with disjoint sets. We show that for positive integers a and b, every bipartite planar graph is (a:b)-choosable iff (a)/(b) ≥ 3. For general planar graphs, we show that if (a)/(b) < 4(2)/(5), then there exists a planar graph that is not (a:b)-choosable, thus improving on a result of X. Zhu, which had 4(2)/(9). Lastly, we show that every K5-minor-free graph is (a:b)-choosable iff (a)/(b) ≥ 5. Along the way, we mention some open problems.