1. bookAHEAD OF PRINT
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2083-5892
Erstveröffentlichung
13 Apr 2013
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
access type Uneingeschränkter Zugang

Countable Graphs Are Majority 3-Choosable

Online veröffentlicht: 21 Jan 2021
Volumen & Heft: AHEAD OF PRINT
Seitenbereich: -
Eingereicht: 31 Mar 2020
Akzeptiert: 06 Nov 2020
Zeitschriftendaten
License
Format
Zeitschrift
eISSN
2083-5892
Erstveröffentlichung
13 Apr 2013
Erscheinungsweise
4 Hefte pro Jahr
Sprachen
Englisch
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.

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

Empfohlene Artikel von Trend MD

Planen Sie Ihre Fernkonferenz mit Scienceendo