The non-3-colorability conjecture for countable undirected multigraphs

An undirected countable multigraph is a countable undirected graph whose edges have weights in N\mathbb{N}. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.