Edge separators for graphs excluding a minor

Gwenaël Joret ; William Lochet ; Michał T. Seweryn

The electronic journal of combinatorics, Tome 30 (2023) no. 4

Résumé

We prove that every $n$-vertex $K_t$-minor-free graph $G$ of maximum degree $\Delta$ has a set $F$ of $O(t^2(\log t)^{1/4}\sqrt{\Delta n})$ edges such that every component of $G - F$ has at most $n/2$ vertices. This is best possible up to the dependency on $t$ and extends earlier results of Diks, Djidjev, Sýkora, and Vrťo (1993) for planar graphs, and of Sýkora and Vrťo (1993) for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of $G$ is isomorphic to a subgraph of the strong product $H \boxtimes K_{\lfloor p \rfloor}$ for some graph $H$ with treewidth at most $t-2$ and $p = \sqrt{(t-3)\Delta |E(G)|} + \Delta$.

Détail

DOI : 10.37236/11744

Classification : 05C83, 05C60, 05C76
Mots-clés : Jacobi-Trudi identities for Foley-King factorial characters, bounded-genus graphs, line graphs