8
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is now findstat.org/St001395 $\endgroup$ – Martin Rubey May 23 at 12:50
  • $\begingroup$ @MartinRubey What is the relationship between findstat and OEIS? $\endgroup$ – Gordon Royle May 24 at 0:39
  • $\begingroup$ OEIS has information associated with integer sequences, FindStat has information associated with 'combinatorial statistics' (if you prefer: 'parameters on combinatorial objects') and maps between combinatorial objects. Thus, the two 'databases' are quite complementary. For example, OEIS might have the number of graphs on $n$ vertices without a strict unfriendly partition, whereas FindStat has, for each such graph the number of strict unfriendly partitions. -- does this answer the question, or are you wondering about something else? $\endgroup$ – Martin Rubey May 24 at 5:30
  • $\begingroup$ @MartinRubey Yes, that answers my question... I was wondering whether they were complementary, overlapping, or competing! $\endgroup$ – Gordon Royle May 27 at 1:14
5
$\begingroup$

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$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.