The non-3-colorability conjecture for countable undirected multigraphs
The non-3-colorability conjecture for countable undirected multigraphs
An undirected countable multigraph is a countable undirected graph whose edges have weights in . A majority coloring is a coloring such that, at every vertex, the total weight of bichromatic incident edges is at least the total weight of monochromatic incident edges.
Multigraph non-3-colorability conjecture. There exists an undirected countable multigraph that is not majority 3-colorable.
Finite multigraphs are majority 2-colorable by a max-cut argument, but the directed construction in the paper does not directly transfer to multigraphs. The asserted countable example remains open in the source.
Sources & referencesView supporting material
Primary source
Bartłomiej Bosek and Aleksander Katan, “A Note About Majority Colorings of Countable DAGs”, arXiv:2406.04189 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.