Coarse Balanced Separators in Fat-Minor-Free Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911588503519232 |
|---|---|
| author | Bonnet, Édouard Le, Hung Pilipczuk, Marcin Pilipczuk, Michał |
| author_facet | Bonnet, Édouard Le, Hung Pilipczuk, Marcin Pilipczuk, Michał |
| contents | Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just being disjoint. In this paper, we give a coarse analogue of the classic theorem that an $n$-vertex graph excluding a fixed minor admits a balanced separator of size $O(\sqrt{n})$. Specifically, we prove that for every integer $d$, real $\varepsilon>0$, and graph $H$, there exist constants $c$ and $r$ such that every $n$-vertex graph $G$ excluding $H$ as a $d$-fat minor admits a set $S \subseteq V(G)$ that is a balanced separator of $G$ and can be covered by $c n^{\frac{1}{2}+\varepsilon}$ balls of radius $r$ in $G$. Our proof also works in the weighted setting where the balance of the separator is measured with respect to any weight function on the vertices, and is effective: we obtain a randomized polynomial-time algorithm to compute either such a balanced separator, or a $d$-fat model of $H$ in $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11318 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Coarse Balanced Separators in Fat-Minor-Free Graphs Bonnet, Édouard Le, Hung Pilipczuk, Marcin Pilipczuk, Michał Combinatorics Discrete Mathematics Data Structures and Algorithms Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just being disjoint. In this paper, we give a coarse analogue of the classic theorem that an $n$-vertex graph excluding a fixed minor admits a balanced separator of size $O(\sqrt{n})$. Specifically, we prove that for every integer $d$, real $\varepsilon>0$, and graph $H$, there exist constants $c$ and $r$ such that every $n$-vertex graph $G$ excluding $H$ as a $d$-fat minor admits a set $S \subseteq V(G)$ that is a balanced separator of $G$ and can be covered by $c n^{\frac{1}{2}+\varepsilon}$ balls of radius $r$ in $G$. Our proof also works in the weighted setting where the balance of the separator is measured with respect to any weight function on the vertices, and is effective: we obtain a randomized polynomial-time algorithm to compute either such a balanced separator, or a $d$-fat model of $H$ in $G$. |
| title | Coarse Balanced Separators in Fat-Minor-Free Graphs |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.11318 |