Skip to main content
2 of 3
fixed grammar, removed general relativity tag, and added more tags.
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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 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)$?