Matching, Covering and Packing (Graph Theory, Chapter 2)

• k-factor = 全域部分グラフであって，全頂点の次数が k

2 部グラフのマッチング

• 2 部マッチングのサイズ ＝ 頂点被覆のサイズ
• $|N(S)| \geq |S|$ for all $S \subseteq A$
• stable matching は常に存在

一般グラフのマッチング

• G が 1-factor 持つ ⇔ $q(G-S) \leq |S|$ for all $S \subseteq V(G)$
  • q(G-S) := 奇数頂点数の連結成分数

パッキング，カバーリング

• packing, covering (グラフクラス H というのが与えられて)
• Erdos-Posa property

木のパッキング

• Arboricity: グラフ G の分割であって森たちにする最小の個数
  • maximum local density の指標
  • star-arboricity とか亜種がある
• Path cover