The non-3-colorability conjecture for countable undirected multigraphs

About 2 years old · traced to

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.

References

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.