Bounding branch-width
Summary: 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.
- Testing branch-width
- Bounding connected tree-width
- Bounds for Width Two Branching Programs
- scientific article; zbMATH DE number 1990711
- Branchwidth of chordal graphs
- Treewidth lower bounds with brambles
- Algorithms – ESA 2005
- Girth and treewidth
- Rank‐width is less than or equal to branch‐width
- Tree-width dichotomy
- Branch-width and well-quasi-ordering in matroids and graphs.
- Branchwidth of graphic matroids
- Call routing and the ratcatcher
- Characterizing graphs of small carving-width
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 3777562 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- On the excluded minors for the matroids of branch-width \(k\)
- Recognising graphic and matroidal connectivity functions
- The branchwidth of graphs and their cycle matroids
This page was built for publication: Bounding branch-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6133165)
