Published October 2020
| Version Submitted + Published
Journal Article
Open
Unfriendly colorings of graphs with finite average degree
Creators
-
1.
Carnegie Mellon University
-
2.
California Institute of Technology
Abstract
In an unfriendly coloring of a graph the color of every node mismatches that of the majority of its neighbors. We show that every probability measure preserving Borel graph with finite average degree admits a Borel unfriendly coloring almost everywhere. We also show that every bounded degree Borel graph of subexponential growth admits a Borel unfriendly coloring.
Additional Information
© 2020 The Authors. The publishing rights in this article are licensed to the London Mathematical Society under an exclusive licence. Received 13 March 2019; published online 9 May 2020. Clinton T. Conley was supported by NSF grant DMS-1500906. Omer Tamuz was supported by a grant from the Simons Foundation (#419427).Attached Files
Published - plms.12345.pdf
Submitted - 1903.05268.pdf
Files
1903.05268.pdf
Additional details
Identifiers
- Eprint ID
- 100889
- Resolver ID
- CaltechAUTHORS:20200124-090354536
Related works
- Describes
- https://arxiv.org/abs/1903.05268 (URL)
Funding
- NSF
- DMS-1500906
- Simons Foundation
- 419427
Dates
- Created
-
2020-01-24Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field
Caltech Custom Metadata
- Caltech groups
- Mathematics Department