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

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 reversreverse 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 reachreaching 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. henceHence 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? andAnd is there any closer relation between $bw(G)$ and $\omega(G)$?

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

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

Source Link

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