2024/06/06 by Bartłomiej Bosek, Bosek, Bartłomiej, Aleksander Katan +1
Mathematics · #05C15 #05C20 #05C63 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · pdf · doi:10.48550/arxiv.2406.04189
openalex publication_date 2024/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A majority coloring of an undirected graph is a vertex coloring in which for each vertex there are at least as many bi-chromatic edges containing that vertex as monochromatic ones. It is known that for every countable graph a majority 3-coloring always exists. The Unfriendly Partition Conjecture states that every countable graph admits a majority 2-coloring. Since the 3-coloring result extends to countable DAGs, a variant of the conjecture states that 2 colors are enough to majority color every countable DAG. We show that this is false by presenting a DAG for which 3 colors are necessary. Presented construction is strongly based on a StackExchange conversation regarding labellings of infinite graphs that is linked in the references.