Unfriendly partitions when avoiding vertices of finite degree

An unfriendly partition of a graph $G = (V,E)$ is a function $c: V \to 2$ such that $|\{x\in N(v): c(x)\neq c(v)\}|\geq |\{x\in N(v): c(x)=c(v)\}|$ for every vertex $v\in V$, where $N(v)$ denotes its neighborhood. It was conjectured by Cowan and Emerson [] that every graph has an unfriendly partition, but Milner and Shelah in [] found counterexamples for that statement by analysing graphs with uncountably many vertices. Curiously, none of their graphs have vertices with finite degree. Therefore, as a natural direction to approach, in this paper we search for the least cardinality of a graph with this property and that admits no unfriendly partitions. Actually, among some other independence results, we conclude that this value cannot be precisely determined within $\textrm {ZFC}$, in the sense that it may vary from model to model of set theory.

Automated summary

This paper investigates the problem of unfriendly partitions in graphs, seeking the minimum cardinality of a graph that satisfies certain criteria and has no unfriendly partitions. The authors found counterexamples by studying graphs with uncountably many vertices, and concluded that this value may vary across different models of set theory.