Skip to main content
2 of 5
edited body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

No, your inequality does not hold. You are off by a constant factor. Probably the easiest way to see this is to consider the dual notion of a tangle, which I will define now.

A separation in a graph $G$ is a pair $(A,B)$ where $A$ and $B$ are edge-disjoint subgraphs of $G$ whose union is $G$. The order of $(A,B)$ is $|V(A) \cap V(B)|$. A tangle $\mathcal{T}$ of order $\theta$ in $G$ is a collection of separations of $G$ satisfying the following axioms.

  1. For all $(A,B) \in \mathcal{T}$, the order of $(A,B)$ is less than $\theta$,

  2. If the order of $(A,B)$ is less than $\theta$, then exactly one of $(A,B)$ or $(B,A)$ is in $\mathcal{T}$,

  3. If $(A,B) \in \mathcal{T}$, then $V(A) \neq V(G)$,

  4. If $(A_1, B_1), (A_2, B_2), (A_3, B_3) \in \mathcal{T}$, then $A_1 \cup A_2 \cup A_3 \neq G$.

Theorem (Robertson and Seymour). The maximum order of a tangle of $G$ is the branch-width of $G$.

It is easy to check that in $K_n$, the set of all separations $(A,B)$ where $|V(A)| < \lceil \frac{2n}{3} \rceil$ is a tangle $\mathcal{T}$ of order $\lceil \frac{2n}{3} \rceil$. Moreover, $\mathcal{T}$ is a maximum order tangle in $K_n$. See Graph Minors X, (4,4) for more details.

Note that branch-width does not increase when passing to subgraphs, so we get the inequality $\frac{2}{3} \omega(G) \leq bw(G)$. More generally, branch-width does not increase when passing to minors, so we can replace $\omega(G)$ in the above inequality by the Hadwiger number of $G$ (the size of a largest clique-minor).

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187