1. bookAHEAD OF PRINT
Dettagli della rivista
License
Formato
Rivista
eISSN
2083-5892
Prima pubblicazione
13 Apr 2013
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
access type Accesso libero

Countable Graphs Are Majority 3-Choosable

Pubblicato online: 21 Jan 2021
Volume & Edizione: AHEAD OF PRINT
Pagine: -
Ricevuto: 31 Mar 2020
Accettato: 06 Nov 2020
Dettagli della rivista
License
Formato
Rivista
eISSN
2083-5892
Prima pubblicazione
13 Apr 2013
Frequenza di pubblicazione
4 volte all'anno
Lingue
Inglese
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

Articoli consigliati da Trend MD

Pianifica la tua conferenza remota con Sciendo