DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Haslegrave

John Haslegrave

University of Warwick, Coventry

email: j.haslegrave@cantab.net

0000-0002-9991-7120

Title:

Countable graphs are majority 3-choosable

PDF

Source:

Discussiones Mathematicae Graph Theory 43(2) (2023) 499-506

Received: 2020-03-31 , Revised: 2020-11-06 , Accepted: 2020-11-06 , Available online: 2020-12-10 , https://doi.org/10.7151/dmgt.2383

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:

majority colouring, unfriendly partition, list colouring

References:

  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.
Close