パーフェクトグラフ定理

同義語:完全グラフ定理弱パーフェクトグラフ定理perfect graph theoremweak perfect graph theorem

概要

パーフェクトグラフ定理(perfect graph theorem)とは、グラフがパーフェクトであること、すなわちすべての誘導部分グラフで彩色数がクリーク数に等しいことと、その補グラフがパーフェクトであることが同値であるという Lovász の定理である。補グラフでは、頂点をクリークに分ける最小個数が独立集合の最大の大きさに等しいという主張になり、二部グラフに当てると Kőnig の定理、比較可能グラフに当てると Mirsky の定理から Dilworth の定理が出る。頂点の複製の補題で証明でき、長さ 5 以上の奇閉路とその補グラフを誘導部分グラフに含まないことによる特徴づけ(強パーフェクトグラフ定理)へつながる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 彩色数, 誘導部分グラフ, 補グラフ

グラフの頂点を、隣り合う頂点が同じ色にならないように塗るには、少なくとも最大のクリーク(どの 2 頂点も隣り合う頂点の集合)の大きさだけの色が要る。この自明な下界がグラフ自身とそのすべての誘導部分グラフで等号になるとき、グラフは パーフェクト(perfect)であるという。パーフェクトグラフ定理(perfect graph theorem)は、L. Lovász が 1972 年に証明した次の定理である。

グラフがパーフェクトであることと、その補グラフがパーフェクトであることは同値である。
補グラフでは、クリークと独立集合(どの 2 頂点も隣り合わない頂点の集合)が入れ替わり、彩色は「頂点をクリークに分けること」に入れ替わる。したがって定理は、「すべての誘導部分グラフで、彩色数が最大クリークの大きさに等しい」なら「すべての誘導部分グラフで、頂点を覆うクリークの最小個数が最大独立集合の大きさに等しい」という、一見別の最小最大定理を導く。二部グラフに当てると マッチング(グラフ理論) の Kőnig の定理が、半順序集合の比較可能グラフに当てると Mirskyの定理 から Dilworthの定理 が出てくる。
この記事では、頂点の複製の補題を使う証明(Lovász の原証明の考え方による)を述べ、さらに強い特徴づけ $|V(H)|\le\alpha(H)\,\omega(H)$ を線形代数で示す証明を添える。後者は補グラフについて対称なので、定理の 2 つ目の証明になる。最後に、奇閉路とその補グラフによる特徴づけ(強パーフェクトグラフ定理)の主張と所在を述べる。

名前と分担

perfect graph を「完全グラフ」と訳すことがあり、この定理も「完全グラフ定理」とよばれることがある。しかし、どの 2 頂点も隣り合うグラフ $K_n$ の名前としての 完全グラフ とは別の概念なので、この記事ではパーフェクトグラフと書く。後で述べる強パーフェクトグラフ定理と区別するため、この定理を 弱パーフェクトグラフ定理 ともいう。
パーフェクトグラフの定義と、$P_4$ を誘導部分グラフに含まないグラフがパーフェクトであることは 誘導部分グラフ の記事の節「彩色数とクリーク数」にある。比較可能グラフがパーフェクトであることは Mirskyの定理 の記事にも注意がある。この記事は補グラフについての定理を主題とする。

定義

以下、グラフは有限で、ループと多重辺をもたないとする。頂点の集合 $W\subseteq V(G)$ が誘導する部分グラフを $G[W]$、$G-W:=G[V(G)\setminus W]$ と書き、$\overline G$ を補グラフとする。

4 つの数

グラフ $G$ について、次のように定める(頂点のないグラフではすべて $0$ とする)。

  1. $\omega(G)$:クリーク数。クリークの頂点数の最大値。
  2. $\alpha(G)$:独立数。独立集合の頂点数の最大値。
  3. $\chi(G)$:彩色数。頂点を独立集合に分けるときの個数の最小値(彩色数)。
  4. $\theta(G)$:クリーク被覆数。頂点をクリークに分けるときの個数の最小値。
基本の関係

すべてのグラフ $G$ について、$\omega(\overline G)=\alpha(G)$、$\chi(\overline G)=\theta(G)$、$\chi(G)\ge\omega(G)$、$\theta(G)\ge\alpha(G)$、$\chi(G)\,\alpha(G)\ge|V(G)|$ が成り立つ。

証明を開く

$W$ が $\overline G$ のクリークであることと $G$ の独立集合であることは同値で、独立集合とクリークも同様に入れ替わるので、前の 2 つが従う。クリークの頂点はすべて異なる色を要するので $\chi\ge\omega$ であり、独立集合はどのクリークとも高々 1 点でしか交わらないので $\theta\ge\alpha$ である。最後の不等式は、$\chi(G)$ 個の色の類がどれも $\alpha(G)$ 個以下の頂点しか含まないことによる。$\square$

パーフェクトグラフ

グラフ $G$ が パーフェクト であるとは、$G$ のすべての誘導部分グラフ $H$ で $\chi(H)=\omega(H)$ となることをいう。

$G$ 自身も誘導部分グラフに含める。定義から、パーフェクトグラフの誘導部分グラフはパーフェクトである。lem-pgt-basic により、$\overline G$ がパーフェクトであることは、$G$ のすべての誘導部分グラフ $H$ で $\theta(H)=\alpha(H)$ となることと同値である($\overline G$ の誘導部分グラフは $\overline{H}$ の形をしている)。

例

パーフェクトなグラフとそうでないグラフ
  1. 完全グラフ $K_n$ は $\chi=\omega=n$ で、誘導部分グラフも完全グラフなのでパーフェクトである。辺のないグラフ $E_n$ も $\chi=\omega=1$($n\ge1$)でパーフェクトである。
  2. 二部グラフ はパーフェクトである。誘導部分グラフも二部グラフで、辺があれば $\chi=\omega=2$、辺がなく頂点があれば $\chi=\omega=1$ だからである。
  3. 長さ $2k+1$($k\ge2$)の閉路 $C_{2k+1}$ はパーフェクトでない。$\omega(C_{2k+1})=2$ だが、奇閉路は 2 色で塗れないので $\chi(C_{2k+1})=3$ である。
  4. その補グラフ $\overline{C_{2k+1}}$($k\ge2$)もパーフェクトでない。$C_{2k+1}$ の独立集合は 1 つおきに選んだ頂点で、高々 $k$ 個なので $\alpha(C_{2k+1})=k$ である。$C_{2k+1}$ のクリークは 1 頂点か 1 辺なので、$2k+1$ 個の頂点を覆うにはクリークが $k+1$ 個以上要り、$\theta(C_{2k+1})=k+1$ である。よって $\omega(\overline{C_{2k+1}})=k$、$\chi(\overline{C_{2k+1}})=k+1$ である。$C_5$ は自分の補グラフと同型である。

二部グラフの補グラフがパーフェクトであることは、すでに非自明な定理である。

二部グラフの補グラフと Kőnig の定理

二部グラフ $B$ について、$\theta(B)=\alpha(B)$ は、最大マッチングの大きさ $\nu(B)$ と最小頂点被覆の大きさ $\tau(B)$ が等しいことと同値である。したがって、二部グラフの補グラフがパーフェクトであることは、Kőnig の定理(マッチング(グラフ理論) の定理「二部グラフの最大マッチングと最小頂点被覆」、$\nu=\tau$)と同値である。

辺と頂点で覆う

$n:=|V(B)|$ とする。$B$ には三角形がないので、クリークは 1 頂点か 1 辺である。頂点をクリークに分けるとき、辺のクリークの集合はマッチングで、それが $j$ 本なら個数は $j+(n-2j)=n-j$ なので、$\theta(B)=n-\nu(B)$ である。また、$U$ が頂点被覆であることと $V(B)\setminus U$ が独立集合であることは同値なので、$\alpha(B)=n-\tau(B)$ である。よって $\theta(B)=\alpha(B)$ と $\nu(B)=\tau(B)$ は同値である。二部グラフの誘導部分グラフは二部グラフなので、すべての誘導部分グラフでの等式は Kőnig の定理と同値であり、def-pgt-perfect の後の注意から後半が従う。$\square$

この命題とパーフェクトグラフ定理を合わせると、「二部グラフはパーフェクト」という自明な事実から Kőnig の定理が導かれる。

頂点の複製の補題

グラフ $G$ の頂点 $x$ について、新しい頂点 $x'$ を加え、$x'$ を $x$ と $x$ の隣接頂点すべてに辺で結んだグラフを $G'$ とする。$G'$ は $G$ から $x$ を複製 して得られるという。

頂点の複製の補題

パーフェクトなグラフから頂点を 1 つ複製して得られるグラフはパーフェクトである。

複製した頂点を色の類に入れる

$G$ の頂点数についての帰納法による。$G=K_1$ なら $G'=K_2$ でパーフェクトである。$G$ をパーフェクト、$|V(G)|\ge2$ とし、$x$ を複製して $G'$ を得たとする。
$G'$ の $G'$ 自身でない誘導部分グラフ $H'$ はパーフェクトである。実際、$x$ と $x'$ の高々一方しか含まなければ、$H'$ は $G$ の誘導部分グラフと同型になる($x'$ を含むときは $x'$ を $x$ に取り替える。$x'$ の $x$ 以外の隣接頂点は $x$ の隣接頂点と同じである)。両方を含めば、$H'$ は $G$ の真の誘導部分グラフ $H'-x'$ から $x$ を複製したもので、帰納法の仮定によりパーフェクトである。よって $\chi(G')\le\omega(G')$ を示せばよい。
$\omega:=\omega(G)$ とおく。$G'$ のクリークから $x'$ を除くか、$x'$ を $x$ に取り替えると $G$ のクリークになるので、$\omega(G')\in\{\omega,\omega+1\}$ である。$\omega(G')=\omega+1$ なら、$G$ を $\chi(G)=\omega$ 色で塗り、$x'$ に新しい色を塗れば $\chi(G')\le\omega+1$ である。
$\omega(G')=\omega$ とする。このとき $x$ は $G$ の大きさ $\omega$ のクリークに含まれない(含まれれば $x'$ を加えて大きさ $\omega+1$ のクリークができる)。$G$ を $\omega$ 色で塗り、$x$ の色の類を $X$ とする。大きさ $\omega$ のクリーク $K$ の頂点はすべて異なる色なので、$K$ は $\omega$ 個の色の類のすべてと交わり、とくに $X$ と交わるが、その点は $x$ ではない。よって $K$ は $X\setminus\{x\}$ と交わり、$H:=G-(X\setminus\{x\})$ は大きさ $\omega$ のクリークをもたず、$\omega(H)\le\omega-1$ である。$H$ はパーフェクトなので $\omega-1$ 色で塗れる。
$X$ は $x$ を含む独立集合なので、$x$ の隣接頂点は $X$ に属さない。$x'$ の隣接頂点は $x$ と $x$ の隣接頂点だけなので、$(X\setminus\{x\})\cup\{x'\}$ は $G'$ の独立集合である。$V(G')$ は $V(H)$ とこの集合の和なので、この集合に新しい 1 色を塗れば $G'$ は $\omega$ 色で塗れ、$\chi(G')\le\omega=\omega(G')$ である。$\square$

$x'$ は $x$ と同じ隣接頂点をもち $x$ とも隣り合うので、$x'$ をさらに複製することは $x$ を複製し直すことと同じである。補題を繰り返すと、頂点 $v$ を大きさ $m_v\ge1$ のクリークに置き換え($v$ と $w$ が隣り合うなら、置き換えたクリークどうしのすべての頂点を結ぶ)たグラフもパーフェクトである。

主定理

パーフェクトグラフ定理

グラフ $G$ がパーフェクトであることと、補グラフ $\overline G$ がパーフェクトであることは同値である。

最大独立集合をばらばらにする

$\overline{\overline G}=G$ なので、$G$ がパーフェクトなら $\overline G$ もパーフェクトであることを示せばよい。def-pgt-perfect の後の注意により、$G$ のすべての誘導部分グラフ $H$ で $\theta(H)\le\alpha(H)$ を示せばよい(逆向きは lem-pgt-basic)。まず次を示す。
(★) パーフェクトなグラフ $H$(頂点が 1 個以上)には、$H$ のすべての最大独立集合(大きさ $\alpha(H)$ の独立集合)と交わるクリーク $K$ がある。
$H$ の最大独立集合の全体を $\mathcal A=\{A_1,\dots,A_m\}$、$\alpha:=\alpha(H)$ とする。各 $A\in\mathcal A$ の元の「写し」を別々に用意する。すなわち $U:=\{(v,A)\mid A\in\mathcal A,\ v\in A\}$ を頂点の集合とし、$(u,A)$ と $(v,B)$ を、「$u=v$ かつ $A\ne B$」または「$uv$ が $H$ の辺」のとき辺で結んだグラフを $H'$ とする。各 $v$ の写しの集合 $U_v:=\{(v,A)\mid v\in A\in\mathcal A\}$ はクリークで、$uv$ が辺なら $U_u$ と $U_v$ の頂点はすべて隣り合う。したがって $H'$ は、$W:=A_1\cup\dots\cup A_m$ として $H[W]$ の各頂点 $v$ を大きさ $|U_v|$ のクリークに置き換えたグラフであり、$H[W]$ はパーフェクトなので、lem-pgt-replication とその後の注意により $H'$ はパーフェクトである。
$A'_i:=\{(v,A_i)\mid v\in A_i\}$ とおくと、$A'_1,\dots,A'_m$ は $U$ を分割し、どれも大きさ $\alpha$ の独立集合である。一方、$H'$ の独立集合 $I$ は各 $U_v$ と高々 1 点で交わり、$I$ が交わる $U_v$ の $v$ たちは $H$ で互いに隣り合わないので、$|I|\le\alpha$ である。よって $\alpha(H')=\alpha$ で、lem-pgt-basic から $\chi(H')\ge|U|/\alpha=m$ である。$H'$ はパーフェクトなので $\omega(H')=\chi(H')\ge m$ であり、$m$ 個以上の頂点をもつクリーク $K'$ がとれる。$K'$ は独立集合 $A'_i$ のそれぞれと高々 1 点で交わり、$A'_1,\dots,A'_m$ が $U$ を分割するので、すべての $A'_i$ と交わる。
$K:=\{v\mid K'\cap U_v\ne\emptyset\}$ とおく。$K$ の相異なる 2 頂点 $v,w$ について、$K'$ の頂点 $(v,A)$、$(w,B)$ は $H'$ で隣り合い $v\ne w$ なので、$vw$ は $H$ の辺である。よって $K$ は $H$ のクリークである。$K'$ が $A'_i$ の点 $(v,A_i)$ を含めば $v\in K\cap A_i$ なので、$K$ はすべての $A_i$ と交わる。これで (★) が示された。
$G$ の誘導部分グラフ $H$ について、$\theta(H)\le\alpha(H)$ を頂点数の帰納法で示す。頂点がなければ両辺は $0$ である。そうでなければ $H$ はパーフェクトなので、(★) のクリーク $K$ がとれる。$H-K$ の独立集合は $K$ と交わらない $H$ の独立集合で、$H$ の最大独立集合はすべて $K$ と交わるから、$\alpha(H-K)\le\alpha(H)-1$ である。$H-K$ も $G$ の誘導部分グラフで頂点が少ないので、帰納法の仮定から $H-K$ は $\alpha(H)-1$ 個以下のクリークに分けられ、$K$ を加えて $\theta(H)\le\alpha(H)$ を得る。$\square$

証明の所在

定理は Die25 Theorem 5.5.4(p. 142)で、同書は Lovász(1972)に帰し、もと Berge の弱パーフェクトグラフ予想であったと述べている。上の証明は同書の 1 つ目の証明(頂点の複製の補題は Lemma 5.5.5、p. 142)を細部を補って書き直したもので、同書の注(p. 154)によれば、Ramírez-Alfonsín・Reed 編の論文集の Preissmann・Sebő の論説から採られている。

Lovász の特徴づけ

次の定理は条件が $G$ と $\overline G$ について対称なので($\alpha$ と $\omega$ が入れ替わるだけ)、パーフェクトグラフ定理の 2 つ目の証明を与える。

頂点数による特徴づけ

グラフ $G$ がパーフェクトであることは、$G$ のすべての誘導部分グラフ $H$ で
$$ |V(H)|\le\alpha(H)\,\omega(H) $$
となることと同値である。

0 と 1 の行列の階数
証明を開く

必要性:$G$ がパーフェクトなら、lem-pgt-basic により $|V(H)|\le\alpha(H)\chi(H)=\alpha(H)\omega(H)$ である。

十分性を頂点数 $n$ の帰納法で示す。すべての誘導部分グラフで不等式が成り立つが $G$ はパーフェクトでないとし、矛盾を導く。帰納法の仮定により $G$ の真の誘導部分グラフはすべてパーフェクトなので、$\chi(G)>\omega(G)$ である。$\alpha:=\alpha(G)$、$\omega:=\omega(G)$ とおく。

(1) 空でない独立集合 $S$ について $\chi(G-S)=\omega(G-S)=\omega$ である。前の等号は $G-S$ がパーフェクトだからである。$\omega(G-S)< \omega$ なら、$G-S$ を $\omega-1$ 色で塗り $S$ に 1 色を足して $\chi(G)\le\omega$ となり矛盾する。

(2) 頂点 $u$ と、$G-u$ の $\omega$ 色の塗り分けを考える((1) で $S=\{u\}$)。大きさ $\omega$ のクリーク $K$ は、$u\notin K$ なら $\omega$ 個の色の類すべてと交わり、$u\in K$ なら $K\setminus\{u\}$ の $\omega-1$ 点がちょうど 1 つの類を除くすべてと交わる。

大きさ $\alpha$ の独立集合 $A_0=\{u_1,\dots,u_\alpha\}$ をとり、各 $j$ について $G-u_j$ の $\omega$ 色の塗り分けの色の類を並べて、独立集合 $A_0,A_1,\dots,A_{\alpha\omega}$ を作る。各 $i$ について (1) により $G-A_i$ は大きさ $\omega$ のクリーク $K_i$ をもつ。

(3) 大きさ $\omega$ のクリーク $K$ は、$A_0,\dots,A_{\alpha\omega}$ のちょうど 1 つと交わらない。実際、$K\cap A_0=\emptyset$ なら、$K$ はどの $u_j$ も含まないので (2) により各塗り分けのすべての類と交わり、交わらないのは $A_0$ だけである。$K\cap A_0\ne\emptyset$ なら、$A_0$ は独立なので $K\cap A_0=\{u_j\}$ の 1 点で、(2) により $K$ は $G-u_j$ の塗り分けのちょうど 1 つの類と交わらず、ほかの塗り分けの類とはすべて交わる。

$N:=\alpha\omega+1$ とし、$A_i$ の頂点の指示ベクトルを行とする $N\times n$ 行列を $P$、$K_j$ の指示ベクトルを列とする $n\times N$ 行列を $Q$ とする。$(PQ)_{ij}=|A_i\cap K_j|$ で、独立集合とクリークは高々 1 点で交わる。$K_i\cap A_i=\emptyset$ で、(3) により $K_j$ が交わらないのは $A_j$ だけなので、$PQ=J-I$($J$ はすべての成分が $1$ の行列)である。$J-I$ の固有値は $N-1$ と $-1$ で $N\ge2$ なので正則であり、$N=\operatorname{rank}(PQ)\le\operatorname{rank}P\le n$ となる。これは $H=G$ での不等式 $n\le\alpha\omega$ に反する。$\square$

この定理と証明は Die25 Theorem 5.5.6(pp. 144–145)にあり、同書は定理を Lovász(1972)に、証明を Gasparian(1996)に帰している(p. 142、p. 154)。

強パーフェクトグラフ定理

ex-pgt-examples の 3・4 により、長さ $5$ 以上の奇閉路とその補グラフはパーフェクトでない。パーフェクトグラフの誘導部分グラフはパーフェクトなので、これらを誘導部分グラフに含むグラフはパーフェクトでない。逆が成り立つというのが次の定理である。

強パーフェクトグラフ定理(主張と所在)

グラフ $G$ がパーフェクトであることは、$G$ も $\overline G$ も長さ $5$ 以上の奇閉路を誘導部分グラフとして含まないことと同値である。

所在と証明の範囲

これは Die25 Theorem 5.5.3(p. 141)で、同書によれば Berge が 1963 年に予想し、Chudnovsky・Robertson・Seymour・Thomas が証明した(Ann. of Math. 164 (2006), 51–229、同書 p. 154)。必要性は上で示したとおりで、十分性の証明は長く、この記事では扱わない。

条件は $G$ と $\overline G$ について対称なので、強パーフェクトグラフ定理からパーフェクトグラフ定理がただちに従う。誘導部分グラフに現れる長さ $4$ 以上の閉路を 穴、補グラフの穴を 反穴 とよぶと、定理は「パーフェクト ⇔ 奇数長の穴も反穴もない」と言い換えられる(同書 p. 141)。

応用:比較可能グラフと Dilworth の定理

有限半順序集合 $P$ の元を頂点とし、相異なる比較可能な 2 元を辺で結んだグラフを $P$ の 比較可能グラフ $G(P)$ という。$P$ の鎖は $G(P)$ のクリーク、反鎖は独立集合である。

Mirsky の定理から Dilworth の定理へ

有限半順序集合 $P$ の比較可能グラフ $G(P)$ はパーフェクトである。したがって $\overline{G(P)}$ もパーフェクトで、$P$ を鎖に分けるときの最小の個数は反鎖の大きさの最大値に等しい(Dilworthの定理)。

証明を開く

$G(P)$ の頂点の集合 $S$ が誘導する部分グラフは、順序を $S$ に制限した半順序集合の比較可能グラフ $G(S)$ である。Mirskyの定理 により、$S$ は鎖の元の個数の最大値(高さ)$h(S)$ と同じ個数の反鎖に分けられる。これは $\chi(G(S))\le h(S)=\omega(G(S))$ を意味するので、$G(P)$ はパーフェクトである。thm-pgt-main により $\overline{G(P)}$ もパーフェクトで、$\chi(\overline{G(P)})=\omega(\overline{G(P)})$ である。lem-pgt-basic により左辺は $\theta(G(P))$、すなわち $P$ を鎖に分ける最小の個数で、右辺は $\alpha(G(P))$、すなわち最大の反鎖の大きさである。$\square$

このほかにも、すべての長さ $4$ 以上の閉路が弦をもつグラフ(弦グラフ)がパーフェクトであることが Die25 Proposition 5.5.2(p. 140)で証明されている。

反例の表

外す・弱める条件例成り立たなくなること
すべての誘導部分グラフで $\chi=\omega$($G$ 自身だけにする)$C_5$ と $K_3$ の非交和 $G$補グラフでも $\chi=\omega$($\chi(\overline G)=4$、$\omega(\overline G)=3$)
lem-pgt-replication の「パーフェクト」($G$ 自身で $\chi=\omega$ にする)ex-pgt-replication-counter のグラフ複製しても $\chi=\omega$
thm-pgt-lovasz のすべての誘導部分グラフ($G$ 自身だけにする)$C_5$ と $K_1$ の非交和パーフェクト($6\le3\cdot2$ だが $C_5$ で $5>2\cdot2$)
thm-pgt-strong の「誘導」部分グラフ(部分グラフにする)$K_5$「長さ 5 以上の奇閉路を部分グラフに含めばパーフェクトでない」
反例の確認

1 行目:$G=C_5\cup K_3$ では $\omega(G)=3$ で、各成分を 3 色で塗れるので $\chi(G)=3$ である。補グラフは $\overline{C_5}\cong C_5$ と辺のないグラフ $E_3$ の結合(両側の頂点をすべて結んだグラフ)で、結合のクリーク数と彩色数は両側の値の和なので(誘導部分グラフ の記事の命題「$P_4$-free なグラフの彩色数」の証明の結合の場合と同じ議論)、$\omega(\overline G)=2+1=3$、$\chi(\overline G)=3+1=4$ である。
3 行目:$G=C_5\cup K_1$ は $|V(G)|=6$、$\alpha(G)=2+1=3$、$\omega(G)=2$ で $G$ 自身では不等式が成り立つが、誘導部分グラフ $C_5$ では成り立たず、$C_5$ を含むので $G$ はパーフェクトでない。
4 行目:$K_5$ はパーフェクトだが、$5$ 頂点を回る閉路を部分グラフとして含む。この閉路は誘導部分グラフではない(弦がある)。

複製すると色数とクリーク数が一致しない例

閉路 $v_1v_2v_3v_4v_5$ に頂点 $w$ を加え、$w$ を $v_4,v_5,v_1$ と結んだグラフ $G$ を考える。$\omega(G)=3$(三角形 $wv_4v_5$。$v_1$ と $v_4$ は隣り合わないので $4$ 頂点のクリークはない)で、$v_1=v_4=a$、$v_2=v_5=b$、$v_3=w=c$ と塗ると隣り合う頂点の色はすべて異なるので、$\chi(G)=3=\omega(G)$ である。$v_3$ を複製して $G'$ を作ると、$v_3,v_3'$ の共通の隣接頂点 $v_2,v_4$ は隣り合わないので $\omega(G')=3$ のままだが、$\chi(G')=4$ である。実際 $G'$ を 3 色で塗れたとすると、互いに隣り合う $v_3,v_3'$ の 2 色と異なる第 3 の色が、$v_3,v_3'$ の両方に隣り合う $v_2$ と $v_4$ に塗られる。すると $v_1$ と $v_5$ はこの色以外の 2 色を分け合い、$v_1,v_4,v_5$ のすべてと隣り合う $w$ に塗る色がない。$G$ は誘導部分グラフ $C_5$ をもつのでパーフェクトでなく、lem-pgt-replication の仮定は外れている。

頂点数 $6$ 以下のすべてのグラフ(ラベル付きで 6 頂点では 32768 個、1〜6 頂点の合計で 33867 個)について、パーフェクトであることと、補グラフがパーフェクトであること、thm-pgt-lovasz の条件、thm-pgt-strong の条件の 4 つが一致することを計算機で確かめた。上の 3 つの例の数値も同じ計算で確かめた。

関連項目

参考文献

[1]
Reinhard Diestel, Graph Theory, 6th edition, Graduate Texts in Mathematics 173, Springer, 2025, §5.5:Proposition 5.5.2(p. 140)、Theorem 5.5.3(p. 141)、Theorem 5.5.4・Lemma 5.5.5(p. 142)、Theorem 5.5.6(pp. 144–145)、第 5 章の注(p. 154)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する