CaltechAUTHORS
  A Caltech Library Service

Unfriendly colorings of graphs with finite average degree

Conley, Clinton T. and Tamuz, Omer (2020) Unfriendly colorings of graphs with finite average degree. Proceedings of the London Mathematical Society, 121 (4). pp. 828-832. ISSN 0024-6115. https://resolver.caltech.edu/CaltechAUTHORS:20200124-090354536

[img] PDF - Published Version
See Usage Policy.

151Kb
[img] PDF - Submitted Version
See Usage Policy.

107Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200124-090354536

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1112/plms.12345DOIArticle
https://arxiv.org/abs/1903.05268arXivDiscussion Paper
ORCID:
AuthorORCID
Tamuz, Omer0000-0002-0111-0418
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).
Funders:
Funding AgencyGrant Number
NSFDMS-1500906
Simons Foundation419427
Issue or Number:4
Classification Code:2010 Mathematics Subject Classification: 54H05 (primary)
Record Number:CaltechAUTHORS:20200124-090354536
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200124-090354536
Official Citation:Conley, C.T. and Tamuz, O. (2020), Unfriendly colorings of graphs with finite average degree. Proc. London Math. Soc., 121: 828-832. doi:10.1112/plms.12345
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100889
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:24 Jan 2020 20:25
Last Modified:11 May 2020 20:56

Repository Staff Only: item control page