论文标题
可计数图是大多数3个coosable
Countable graphs are majority 3-choosable
论文作者
论文摘要
不友好的分区猜想认为，每个可计数图都允许一个2彩色的图形，其中每个顶点至少有包含该顶点的双重边缘与单色的边缘一样多。这是一般不知道的，但众所周知，与此属性的三色始终存在。 Anholcer，Bosek和Grytczuk最近给出了该猜想的列表彩色版本，并证明了尺寸4列表的着色存在。我们将它们的结果提高到了Size 3的列表；证明扩展到有向的无环图。我们还讨论了一些概括。
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.
