Countable graphs are majority 3-choosable

DOI10.7151/DMGT.2383arXiv2003.10408MaRDI QIDQ6337266

Publication date: 23 March 2020

Abstract: The Unfriendly Partition Conjecture posits that every countable graph admits a 2-colouring in which for each vertex there are at least as many bichromatic edges containing that vertex as monochromatic ones. This is not known in general, but it is known that a 3-colouring with this property always exists. Anholcer, Bosek and Grytczuk recently gave a list-colouring version of this conjecture, and proved that such a colouring exists for lists of size 4. We improve their result to lists of size 3; the proof extends to directed acyclic graphs. We also discuss some generalisations.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Infinite graphs (05C63)

This page was built for publication: Countable graphs are majority 3-choosable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6337266)