Strict unfriendly partitions

Question

Given a graph $G$, an unfriendly partition of $G$ is a partition of $V(G)$ into two classes, such that for every class, every vertex has at least as many neighbors in the other class as in its own class.

It is known that every finite graph has an unfriendly partition (just take a partition maximizing the number of edges between two classes) and not every infinite graph has an unfriendly partition (Milner and Shelah). However, it's open whether every countable graph has an unfriendly partition.

Define a strict unfriendly partition of a graph $G$ to be a partition of $V(G)$ into two classes, such that for each class, each vertex has strictly more neighbours in the other class than in its own class.

Not all finite graphs have strict unfriendly partitions. Indeed, it's easy to see that $K_n$ or $C_n$ has a strict unfriendly partition if and only if $n$ is even.

Is there a characterization of all finite graphs $G$ such that $G$ has a strict unfriendly partition?

Answer 1

This is more an extended comment than an actual answer. If I'm not mistaken, then deciding whether a given graph has a strict unfriendly partition is NP hard, i.e. there probably is no easy-to-decide characterisation. Here is a reduction from 3-SAT to this decision problem.

Given a 3-SAT formula $F$, define a graph $G$ as follows:

• Take a path on 5 vertices $(a,u,b,v,c)$.
• For every variable $x_i$ of $F$ take a path on 4 vertices $(t_i,u_i,v_i,f_i)$, and attach to every $t_i$ and every $f_i$ as many leaves as there are clauses in $F$.
• for every clause $C_j$ of $F$ take a vertex $y_j$ and connect this vertex to $t_i$ if $x_i$ appears in $C_j$, and to $f_i$ if $\lnot x_i$ appears in $C_j$. Furthermore, add edges from $a$, $b$, and $c$ to every $y_j$.

We claim that $G$ has a strict unfriendly partition if and only if $F$ is satisfiable.

Assume that $G$ has a strict unfriendly partition. The vertices $u$,$v$,$u_i$, and $v_i$ make sure that $a,b,c$ end up in the same part whereas $t_i$ and $f_i$ end up in different parts. Denote the part containing $a,b,c$ by $A$.

Since 3 of the 6 neighbours of any $y_j$ are contained in $A$, we know that $y_j \notin A$. Furthermore, at least one of the remaining neighbours must be in $A$, otherwise we wouldn't have a strict unfriendly partition. By construction of $G$, this shows that every clause is satisfied if we set $x_i = \mathrm{true}$ for $t_i \in A$ and $x_i = \mathrm{false}$ for $f_i \in A$, and thus $F$ is satisfiable.

Conversely, assume that $F$ is satisfiable and let $x_i = \hat x_i$ be an assignment of values that satisfies $F$. Define a partition of $V(G)$ by

$$A = \{a,b,c\} \cup \{t_i, v_i, \text{leaves attached to }f_i \mid \hat x_i = \mathrm true\} \cup \{f_i, u_i, \text{leaves attached to }t_i \mid \hat x_i = \mathrm false\},$$ and $B = V(G) \setminus A$. This is strictly unfriendly in $a,b,c,u,v,u_i,v_i$ because all their neighbours are in in the other part, respectively. It is strictly unfriendly in $t_i$ and $f_i$ because the leaves attached to them outweigh the neighbours of the form $y_j$. It is strictly unfriendly in $y_j$ because $a,b,c \in A$ and $x_i = \hat x_i$ was assumed to satisfy $F$ (and thus at least one more neighbour of $y_j$ is contained in $A$).