Journal
JOURNAL OF LOGIC AND COMPUTATION
Volume -, Issue -, Pages -Publisher
OXFORD UNIV PRESS
DOI: 10.1093/logcom/exad070
Keywords
-
Categories
Ask authors/readers for more resources
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.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available