1. bookAHEAD OF PRINT
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
access type Accès libre

Countable Graphs Are Majority 3-Choosable

Publié en ligne: 21 Jan 2021
Volume & Edition: AHEAD OF PRINT
Pages: -
Reçu: 31 Mar 2020
Accepté: 06 Nov 2020
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
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

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo