Geodesic
Countable graphs are majority 3-choosable
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 499-506

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: majority colouring, unfriendly partition, list colouring 
@article{DMGT_2023_43_2_a12,
     author = {Haslegrave, John},
     title = {Countable graphs are majority 3-choosable},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {499--506},
     publisher = {mathdoc},
     volume = {43},
     number = {2},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a12/}
}
TY  - JOUR
AU  - Haslegrave, John
TI  - Countable graphs are majority 3-choosable
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 499
EP  - 506
VL  - 43
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a12/
LA  - en
ID  - DMGT_2023_43_2_a12
ER  - 
%0 Journal Article
%A Haslegrave, John
%T Countable graphs are majority 3-choosable
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 499-506
%V 43
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a12/
%G en
%F DMGT_2023_43_2_a12
Haslegrave, John. Countable graphs are majority 3-choosable. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 499-506. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a12/