Skip to main content
1 of 3

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

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 revers 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 reach the unique edges in leaves. In a clique, all vertices are neighbors and all of them must be appear in labels of edges incident on the root. hence the size of each label on edges that 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)$?