The Library
Countable graphs are majority 3-choosable
Tools
Haslegrave, John (2023) Countable graphs are majority 3-choosable. Discussiones Mathematicae Graph Theory, 43 (2). pp. 499-506. doi:10.7151/dmgt.2383 ISSN 1234-3099.
|
PDF
WRAP-Countable-graphs-majority-3-choosable-Haselgrave-2020.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (686Kb) | Preview |
|
PDF
WRAP-Countable-graphs-majority-3-choosable-Haselgrave-2020.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (205Kb) |
Official URL: https://doi.org/10.7151/dmgt.2383
Abstract
The Unfriendly Partition Conjecture posits that every countable graph admits a -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 -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 . We improve their result to lists of size ; the proof extends to directed acyclic graphs. We also discuss some generalisations.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | |||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring, Graph theory | |||||||||
Journal or Publication Title: | Discussiones Mathematicae Graph Theory | |||||||||
Publisher: | University of Zielona Góra | |||||||||
ISSN: | 1234-3099 | |||||||||
Official Date: | 2023 | |||||||||
Dates: |
|
|||||||||
Volume: | 43 | |||||||||
Number: | 2 | |||||||||
Page Range: | pp. 499-506 | |||||||||
DOI: | 10.7151/dmgt.2383 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Access rights to Published version: | Open Access (Creative Commons) | |||||||||
Date of first compliant deposit: | 9 November 2020 | |||||||||
Date of first compliant Open Access: | 21 December 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
|||||||||
Related URLs: | ||||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year