All graphs are majority 3-choosable

2025/05/09 by Ouborny, Jan, Pitz, Max
#05C15 (Primary) 05C63 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2505.06031

Abstract

Every graph is majority 3-choosable. This generalises the result by Shelah-Milner that every graph has an unfriendly 3-partition, confirming a conjecture of Haslegrave from 2020.

Citations

• Majority choosability of countable graphs

Related

• Majority choosability of countable graphs
• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Choosability with Separation in Complete Multipartite Graphs
• Schnyder woods and Alon-Tarsi number of planar graphs
• 3-choosability of planar graphs with (<=4)-cycles far apart