Unfriendly Partition Conjecture for countably infinite graphs
Unfriendly Partition Conjecture for countably infinite graphs
A majority -vertex-coloring of a graph is a coloring of its vertices with two colors such that, at every vertex, the number of neighbors having the same color is at most the number having the other color. Unfriendly Partition Conjecture. Every countably infinite graph admits a majority -vertex-coloring. This is the countably infinite restriction of the broader Cowan–Emerson conjecture. Every infinite graph admits a majority -vertex-coloring, but whether every countably infinite graph admits a majority -vertex-coloring remains open.
Sources & referencesView supporting material
Primary source
Rafał Kalinowski, Monika Pilśniak and Marcin Stawiski, “List majority edge-colorings of graphs”, arXiv:2312.00922 (2023).
Additional references
2 papers in this index state this conjecture (2020–2023). The statement above is taken from the most recent of them; the others are arXiv:2003.02883.
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.