1. bookAHEAD OF PRINT
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
access type Acceso abierto

Countable Graphs Are Majority 3-Choosable

Publicado en línea: 21 Jan 2021
Volumen & Edición: AHEAD OF PRINT
Páginas: -
Recibido: 31 Mar 2020
Aceptado: 06 Nov 2020
Detalles de la revista
License
Formato
Revista
eISSN
2083-5892
Primera edición
13 Apr 2013
Calendario de la edición
4 veces al año
Idiomas
Inglés
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.

Keywords

MSC 2010

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

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

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

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

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

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

[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.Search in Google Scholar

[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. doi:10.1016/j.jctb.2017.09.00110.1016/j.jctb.2017.09.001Search in Google Scholar

[9] A. Girão, T. Kittipassorn and K. Popielarz, Generalized majority colourings of di-graphs, Combin. Probab. Comput. 26 (2017) 850–855. doi:10.1017/S096354831700044X10.1017/S096354831700044XSearch in Google Scholar

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

[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. doi:10.37236/641010.37236/6410Search in Google Scholar

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

[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.10.1017/CBO9780511983917.031Search in Google Scholar

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

Artículos recomendados de Trend MD

Planifique su conferencia remota con Sciendo