Geodesic
Countable graphs are majority 3-choosable
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 499-506 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2023},
     volume = {43},
     number = {2},
     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
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
%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/

[1] R. Aharoni, E.C. Milner and K. Prikry, Unfriendly partitions of a graph, J. Combin. Theory Ser. B 50 (1990) 1–10. https://doi.org/10.1016/0095-8956(90)90092-E

[2] M. Anholcer, B. Bosek and J. Grytczuk, Majority choosability of digraphs, Electron. J. Combin. 24 (2017) #P3.57. https://doi.org/10.37236/6923

[3] M. Anholcer, B. Bosek and J. Grytczuk, Majority coloring of infinite digraphs, Acta Math. Univ. Comenian. (N.S.) 88 (2019) 371–376.

[4] M. Anholcer, B. Bosek and J. Grytczuk, Majority choosability of countable graphs (2020). arXiv: 2003.02883

[5] E. Berger, Unfriendly partitions for graphs not containing a subdivision of an infinite clique, Combinatorica 37 (2017) 157–166. https://doi.org/10.1007/s00493-015-3261-1

[6] H. Bruhn, R. Diestel, A. Georgakopoulos and P. Sprüssel, Every rayless graph has an unfriendly partition, Combinatorica 30 (2010) 521–532. https://doi.org/10.1007/s00493-010-2590-3

[7] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, in: Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, P.Z. Chinn and D. McCarthy (Ed(s)), (Util. Math., Winnipeg, Man. 1980) 125–157.

[8] Z. Dvořák and L. Postle, Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B 129 (2018) 38–54. https://doi.org/10.1016/j.jctb.2017.09.001

[9] A. Girão, T. Kittipassorn and K. Popielarz, Generalized majority colourings of digraphs, Combin. Probab. Comput. 26 (2017) 850–855. https://doi.org/10.1017/S096354831700044X

[10] F. Knox and R. Šámal, Linear bound for majority colourings of digraphs, Electron. J. Combin. 25 (2018) #P3.29. https://doi.org/10.37236/6762

[11] S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen and D.R. Wood, Majority colourings of digraphs, Electron. J. Combin. 24 (2017) #P2.25. https://doi.org/10.37236/6410

[12] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.

[13] S. Shelah and E.C. Milner, Graphs with no unfriendly partitions, in: A Tribute to Paul Erdős, A. Baker, B. Bollobás and A. Hajnal (Ed(s)), (Cambridge Univ. Press, Cambridge 1990) 373–384.

[14] V.G. Vizing, Vertex colorings with given colors, Diskret. Analiz 29 (1976) 3–10, in Russian.