Bounding branch-width

Susan Jowett ; Jasmine Lulani Kaulamatoa¹ ; Geoff Whittle

¹Victoria University of Wellington

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

Résumé

If $(X,Y)$ is a partition of the vertices of a graph $G=(V,E)$ and there are $k$ edges joining vertices in $X$ to vertices in $Y$, then $(X,Y)$ is an edge separation of $G$ of order $k$. The graph $G$ is $(n,k)$-edge connected, if whenever $(X,Y)$ is an edge separation of $G$ of order at most $k$, then either $X$ or $Y$ has at most $n$ elements. We prove that if $G$ is cubic and $(n,k)$-edge connected, then one can find edges to delete so that the resulting graph is $(6n+2,k)$-edge connected. We find an explicit bound on the size of a cubic graph that is minimal in the immersion order with respect to having carving-width $k$. The techniques we use generalise techniques used to prove similar theorems for other structures. In an attempt to develop a unified setting we set up an axiomatic framework to describe certain classes of connectivity functions. We prove a theorem for such classes that gives sufficient conditions to enable a bound on the size of members that are minimal with respect to having branch-width greater than $k$. As well as proving the above mentioned result for edge connectivity in this setting, we prove (known) bounds on the size of excluded minors for the classes of matroids and graphs of branch-width $k$. We also bound the size of a connectivity function that has branch-width greater than $k$ and is minimal with respect to an operation known as elision.

Détail

DOI : 10.37236/11162

Classification : 05C70, 05B35, 05C40
Mots-clés : carving-width, polynomial-time algorithms