Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.18913 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911331534241792 |
|---|---|
| author | DeVos, Matt Nurse, Kathryn |
| author_facet | DeVos, Matt Nurse, Kathryn |
| contents | Let $G$ be a graph and let $\{X_0,X_1\}$ be a partition of $V(G)$. This partition is called external or unfriendly if every $x \in X_i$ has at least as many neighbours in $X_{1-i}$ as in $X_i$. Every maximum edge-cut gives rise to an external partition, so these partitions are always guaranteed to exist. However, it remains a challenge to find such partitions with additional restrictions. Ban and Linial have conjectured that in the case when $G$ is cubic, there always exists an external partition $\{X_0,X_1\}$ for which $-2 \le |X_0| - |X_1| \le 2$. We prove this in two special cases: whenever $G$ can be decomposed into a cycle and a tree, and whenever $G$ has a cubic tree $T$ for which $G - E(T)$ is bipartite. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18913 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Ban-Linial Conjecture DeVos, Matt Nurse, Kathryn Combinatorics 05C15 Let $G$ be a graph and let $\{X_0,X_1\}$ be a partition of $V(G)$. This partition is called external or unfriendly if every $x \in X_i$ has at least as many neighbours in $X_{1-i}$ as in $X_i$. Every maximum edge-cut gives rise to an external partition, so these partitions are always guaranteed to exist. However, it remains a challenge to find such partitions with additional restrictions. Ban and Linial have conjectured that in the case when $G$ is cubic, there always exists an external partition $\{X_0,X_1\}$ for which $-2 \le |X_0| - |X_1| \le 2$. We prove this in two special cases: whenever $G$ can be decomposed into a cycle and a tree, and whenever $G$ has a cubic tree $T$ for which $G - E(T)$ is bipartite. |
| title | On the Ban-Linial Conjecture |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2512.18913 |