What is the relation between size of maximum clique and branchwidth?

Question

Let $bw(G)$ be the branchwidth of graph $G$ and $\omega(G)$ be the size of maximum clique in $G$. I think the following inequality holds: $$ \omega(G)\leq bw(G) $$

Intuition: Assume (in reverse of process of building a branch-decomposition) we are in root of branch-decomposition and want to separate edges to 2 parts recursively with least intersection in vertices until reaching the unique edges in leaves. In a clique, all vertices are neighbors and all of them must appear in labels of edges incident on the root. Hence the size of each label on edges incident on the root must be greater than or equal to size of maximum clique.

Is my intuition right? And is there any closer relation between $bw(G)$ and $\omega(G)$?

Answer 1

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 branchwidth 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 branchwidth does not increase when passing to subgraphs, so we get the inequality $\frac{2}{3} \omega(G) \leq bw(G)$. More generally, branchwidth 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).

Your inequality does holds if you replace branchwidth with treewidth (except for the silly minus one in the definition of treewidth). That is, for every graph $G$, we have $\omega(G)-1 \leq tw(G)$, where $tw(G)$ is the treewidth of $G$. It is well-known that treewidth and branchwidth are within a constant factor of each other.