Published October 2020
| Submitted + Published
Journal Article
Open
Unfriendly colorings of graphs with finite average degree
- Creators
- Conley, Clinton T.
- Tamuz, Omer
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
plms.12345.pdf
Files
(264.3 kB)
Name | Size | Download all |
---|---|---|
md5:d8917f3d9d00c53c97301a0a0b479f03
|
154.7 kB | Preview Download |
md5:38936a41a8cec757d11609136902daf8
|
109.6 kB | Preview Download |
Additional details
- Eprint ID
- 100889
- Resolver ID
- CaltechAUTHORS:20200124-090354536
- DMS-1500906
- NSF
- 419427
- Simons Foundation
- Created
-
2020-01-24Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field