202510102310

Tags : Graph Theory

Crown Decomposition

---

Definition

A Crown Decomposition of a graph $G$ is a partition of the vertex set $V(G)$ into 3 parts, $C,H$ and $R$ such that:

• $C$ is non-empty.
• $C$ is an independent set.
• There are no edges between $C$ and $R$, that is, $H$ separates the other 2 parts
• Let $E^{\prime }$ be the set of edges between $C$ and $H$, then there is matching in $E^{\prime }$ covers $H$.

One can think of $C$ as a crown put on top of the head $H$ and $R$ is the remaining part of the body.

---

References

• Crown Lemma