A Note About Majority Colorings of Countable DAGs
<|reference_start|>A Note About Majority Colorings of Countable DAGs: 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.<|reference_end|>
@article{bosek2024a,
    title={A Note About Majority Colorings of Countable DAGs},
    author={Bart{l}omiej Bosek, Aleksander Katan},
    journal={arXiv preprint arXiv:2406.04189},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.04189},
    primaryClass={cs.DM math.CO}
}