弦グラフ

同義語:chordal graphtriangulated graphrigid circuit graph

概要

弦グラフ(chordal graph)とは、長さ 4 以上のどの閉路も、閉路の上で隣り合わない 2 頂点を結ぶ辺(弦)をもつ有限グラフであり、長さ 4 以上の閉路を誘導部分グラフに含まないことと同値である。弦グラフであることは、どの極小分離集合もクリークであること、隣接頂点がクリークをなす頂点を 1 つずつ取り除けること(完全消去順序)、木の部分木の族の交差グラフであることのそれぞれと同値である。完全消去順序に沿った貪欲法で、極大クリークの列挙、彩色数とクリーク数の一致、最大独立集合とクリーク被覆が得られ、弦グラフとその補グラフはパーフェクトである。

$$\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}} $$

前提知識: グラフ, 誘導部分グラフ, クリーク

弦グラフ(chordal graph)とは、長さ $4$ 以上のどの閉路も 弦(閉路の上で隣り合わない 2 頂点を結ぶ辺)をもつグラフである。言い換えると、誘導部分グラフとして現れる閉路が三角形だけのグラフである。木、完全グラフ、区間グラフ はどれも弦グラフで、$4$ 頂点の閉路 $C_4$ は弦グラフでない。
弦グラフは、完全グラフから始めて完全部分グラフに沿った貼り合わせをくり返して作られるグラフでもある(Die25 Proposition 5.5.1, p. 140)。この構造は 4 通りの同値な特徴づけに表れる。頂点を 1 つずつ取り除く順序(完全消去順序)、2 頂点を分ける頂点集合で包含について極小なもの(極小分離集合)、木の部分木の交差、木分解である。順序による特徴づけから、一般のグラフでは難しい最大クリーク・彩色数・最大独立集合が、弦グラフでは順序に沿った貪欲法で求まる。

結果内容この記事での扱い
lem-cg-separator極小分離集合はクリーク証明する
lem-cg-dirac完全でなければ隣接しない単体的頂点が 2 つある証明する
thm-cg-main4 つの条件の同値証明する
prop-cg-coloring彩色数 $=$ クリーク数、独立数 $=$ クリーク被覆数証明する
prop-cg-cliques極大クリークは頂点数以下証明する

定義

この記事のグラフは、頂点が有限個の単純グラフ $G=(V,E)$ とする。$v\in V$ の隣接頂点の集合を $N(v)$、$N[v]=N(v)\cup\{v\}$ とし、$W\subset V$ について $G[W]$ を誘導部分グラフ、$G-W=G[V\setminus W]$、$G-v=G-\{v\}$ と書く。クリーク数 $\omega(G)$、独立数 $\alpha(G)$、彩色数 $\chi(G)$、クリーク被覆数 $\theta(G)$(頂点をクリークに分けるときの個数の最小値)は パーフェクトグラフ定理 の記事の定義のとおりとする。$k\ge3$ について $C_k$ は $k$ 頂点の閉路グラフである。

弦グラフ

長さ $4$ 以上のどの閉路も弦をもつグラフを 弦グラフ という。

閉路 $x_1x_2\cdots x_kx_1$($k\ge4$)が弦をもたなければ、$G[\{x_1,\dots,x_k\}]$ は $C_k$ である。逆に $G[W]$ が $C_k$ ならその閉路は弦をもたない。したがって、弦グラフであることは、$k\ge4$ のどの $C_k$ も誘導部分グラフとして含まないことと同値である(Die25 §5.5, p. 140)。とくに 弦グラフの誘導部分グラフは弦グラフである。

単体的頂点と完全消去順序
  1. 頂点 $v$ は、$N(v)$ がクリークであるとき 単体的(simplicial)であるという。このとき $N[v]$ もクリークである。
  2. $V$ の並べ方 $v_1,v_2,\dots,v_n$ は、各 $i$ について $v_i$ が $G[\{v_i,v_{i+1},\dots,v_n\}]$ で単体的であるとき、完全消去順序(perfect elimination ordering)という。すなわち、$v_i$ の隣接頂点のうち $v_i$ より後ろのものはクリークをなす。
極小分離集合

隣接しない相異なる 2 頂点 $a,b$ について、$a,b\notin S$ で $G-S$ において $a$ と $b$ が別の連結成分に入る $S\subset V$ を $a$–$b$ 分離集合 という。包含について極小なものを 極小 $a$–$b$ 分離集合 といい、ある $a,b$ についての極小 $a$–$b$ 分離集合を単に 極小分離集合 という。

$a,b$ が隣接しなければ $V\setminus\{a,b\}$ は $a$–$b$ 分離集合なので、極小 $a$–$b$ 分離集合はいつも存在する。

例
  1. 完全グラフ $K_n$ はどの頂点も単体的で、どの並べ方も完全消去順序である。
  2. 木と森 は閉路をもたないので弦グラフである。葉と孤立点は単体的で、葉を順に取り除く並べ方は完全消去順序である。
  3. 区間グラフ は弦グラフである(区間グラフ の Gilmore–Hoffman の定理)。
  4. 分割グラフ:頂点がクリーク $K$ と独立集合 $I$ に分かれるグラフは弦グラフである。実際、$C_k$($k\ge4$)が誘導部分グラフとして現れたとすると、$I$ の頂点は閉路の上で隣り合わないので $K$ の頂点が $k/2\ge2$ 個以上ある。$K$ の 2 頂点は隣接し、誘導された閉路では隣接する 2 頂点は閉路の上で隣り合うので、$K$ の頂点は $2$ 個以下である。よって $k=4$ で、閉路の上に $I,K,I,K$ と交互に並ぶが、$K$ の 2 頂点は閉路の上で隣り合わないのに隣接し、矛盾する。$I$ の頂点を先に、$K$ の頂点を後に並べると完全消去順序になる。
  5. 扇:道 $1-2-\cdots-m$ の全部の頂点に頂点 $0$ を結んだグラフは弦グラフで、$1,2,\dots,m,0$ は完全消去順序である。$i$ の後ろの隣接頂点は $i+1$ と $0$ で、この 2 つは隣接する。

極小分離集合と単体的頂点

極小分離集合はクリーク

$G$ を弦グラフとすると、$G$ のどの極小分離集合もクリークである。

2 つの成分を通る最短の道で閉路を作る

$S$ を極小 $a$–$b$ 分離集合とし、$G-S$ の $a$ を含む連結成分を $C_a$、$b$ を含む連結成分を $C_b$ とする。
各 $s\in S$ は $C_a$ にも $C_b$ にも隣接頂点をもつ. $s$ が $C_a$ に隣接頂点をもたないとする。極小性から $S\setminus\{s\}$ は $a$–$b$ 分離集合でないので、$G-(S\setminus\{s\})$ に $a$ から $b$ への道 $P$ がある。$S$ は分離集合なので $P$ は $s$ を通る。$P$ が最初に $s$ に着く直前までの部分は $a$ から始まり $S$ を通らないので $C_a$ に含まれ、その最後の頂点は $s$ の隣接頂点である($a\ne s$ なので直前の頂点がある)。これは仮定に反する。$C_b$ についても同じである。
クリークであること. $s,t\in S$ が相異なり隣接しないとする。$C_a$ は連結で $s,t$ はどちらも $C_a$ に隣接頂点をもつので、$s$ から $t$ への道で内部の頂点がすべて $C_a$ に入るものがある。そのうち最短のものを $P_a$ とし、同様に $P_b$ をとる。$s,t$ は隣接しないので、どちらの内部も空でない。$P_a$ と $P_b$ をつないだ閉路 $Z$ の長さは $4$ 以上である。$Z$ の弦を考える。$C_a$ と $C_b$ は $G-S$ の別の成分なので、$P_a$ の内部と $P_b$ の内部を結ぶ辺はない。$s,t$ は隣接しない。$P_a$ の 2 頂点を結ぶ $Z$ の弦があれば、それを使って $P_a$ より短い、内部が $C_a$ に入る $s$–$t$ の道ができるので、最短性に反する。$P_b$ も同様である。よって $Z$ は弦をもたず、$G$ が弦グラフであることに反する。$\square$

この議論は Die25 Proposition 5.5.1(p. 140)の証明の中にある。次の補題の単体的頂点の存在は Dirac(1961)による(FG65 p. 851 の引用)。

単体的頂点の存在

弦グラフ $G$ は、完全グラフであるか、または隣接しない 2 つの単体的頂点をもつ。とくに、頂点をもつ弦グラフには単体的頂点がある。

分離集合の両側で帰納法を使う

頂点数 $n$ についての帰納法で示す。$G$ が完全グラフなら示すことはない。そうでないとし、隣接しない $a,b$ と極小 $a$–$b$ 分離集合 $S$ をとる。lem-cg-separator により $S$ はクリークである。$G-S$ の $a$ を含む連結成分を $C_a$ とし、$G_a=G[C_a\cup S]$ とおく。$G_a$ は弦グラフで、$b$ を含まないので頂点数は $n$ より小さい。
$G_a$ が完全グラフなら $a$ は $G_a$ で単体的である。そうでなければ、帰納法の仮定から $G_a$ には隣接しない単体的頂点が 2 つあり、$S$ はクリークなので少なくとも一方は $C_a$ に入る。いずれにしても、$C_a$ の頂点 $v$ で $G_a$ において単体的なものがある。$C_a$ は $G-S$ の連結成分なので、$v$ の $G$ での隣接頂点はすべて $C_a\cup S$ に入り、$N_G(v)=N_{G_a}(v)$ である。よって $v$ は $G$ で単体的である。
同様に $b$ を含む成分 $C_b$ に $G$ で単体的な頂点 $w$ がある。$v,w$ は $G-S$ の別の成分にあるので隣接しない。$\square$

主定理:4 つの特徴づけ

木 $T$ の頂点の集合で、$T$ の誘導部分グラフが連結(したがって木)になる空でないものを $T$ の 部分木 という。部分木の族 $(T_v)_{v\in V}$ について、相異なる $u,v$ を $T_u\cap T_v\ne\emptyset$ のときに隣接させたグラフを、族の 交差グラフ という。
thm-cg-main の証明には、部分木についての次の性質を使う。

部分木の Helly 性

木 $T$ の部分木 $T_1,\dots,T_k$ のどの 2 つも交われば、$T_1\cap\cdots\cap T_k\ne\emptyset$ である。

3 点の中央の頂点

木では 2 頂点 $x,y$ を結ぶ道はただ 1 つで、これを $P(x,y)$ と書く。$x,y$ が部分木 $T_i$ に入れば、$T_i$ の中の道も $P(x,y)$ なので $P(x,y)\subset T_i$ である。とくに 2 つの部分木の共通部分は、空でなければ部分木である。
3 点の中央. 頂点 $x,y,z$ について、$P(z,x)$ を $z$ から進んで最初に $P(x,y)$ に入る頂点を $m$ とする($x\in P(x,y)$ なので存在する)。$P(z,m)$ は $m$ 以外で $P(x,y)$ と交わらないので、$P(z,m)$ と $P(m,x)$、$P(z,m)$ と $P(m,y)$ をつないだものはそれぞれ道であり、一意性から $P(z,x)$、$P(z,y)$ に等しい。よって $m$ は $P(x,y)$、$P(y,z)$、$P(z,x)$ のすべてに入る。
$k=3$. $x\in T_2\cap T_3$、$y\in T_3\cap T_1$、$z\in T_1\cap T_2$ をとる。$P(x,y)\subset T_3$、$P(y,z)\subset T_1$、$P(z,x)\subset T_2$ なので、中央の $m$ は 3 つの部分木すべてに入る。
一般の $k$. $k$ についての帰納法による。$k\le2$ は仮定そのものである。$k\ge3$ のとき、$T'=T_{k-1}\cap T_k$ は空でない部分木で、$i\le k-2$ について $k=3$ の場合を $T_i,T_{k-1},T_k$ に当てると $T_i\cap T'\ne\emptyset$ である。$T_1,\dots,T_{k-2},T'$ に帰納法の仮定を当てればよい。$\square$

弦グラフの特徴づけ

有限グラフ $G$ について、次は同値である。

  1. $G$ は弦グラフである。
  2. $G$ のどの極小分離集合もクリークである。
  3. $G$ は完全消去順序をもつ。
  4. $G$ は、ある木の部分木の族の交差グラフである。
1 ⇒ 2 ⇒ 1、1 ⇒ 3 ⇒ 1、3 ⇒ 4 ⇒ 3

1 ⇒ 2 は lem-cg-separator である。
2 ⇒ 1. $G$ が弦をもたない閉路 $Z$(長さ $4$ 以上)をもつとする。$Z$ の上で隣り合わない 2 頂点 $a,b$ をとると、弦がないので $a,b$ は隣接しない。極小 $a$–$b$ 分離集合 $S$ をとる。$Z$ は $a$ と $b$ を結ぶ 2 本の道に分かれ、どちらの内部も空でない。$S$ は両方の道を断つので、一方の内部の頂点 $x$ と他方の内部の頂点 $y$ を含む。$Z$ は弦をもたないので、$Z$ の 2 頂点が隣接するのは $Z$ の上で隣り合うときに限り、別の道の内部にある $x,y$ は隣接しない。よって $S$ はクリークでなく、2 に反する。
1 ⇒ 3. 頂点数についての帰納法による。lem-cg-dirac により単体的頂点 $v_1$ がある。$G-v_1$ は弦グラフなので、帰納法の仮定から完全消去順序 $v_2,\dots,v_n$ をもつ。$v_1,v_2,\dots,v_n$ は $G$ の完全消去順序である。
3 ⇒ 1. 完全消去順序 $v_1,\dots,v_n$ をとり、長さ $4$ 以上の閉路 $Z$ をとる。$Z$ の頂点のうち番号が最小のものを $v_i$ とし、$Z$ の上での $v_i$ の両隣を $x,y$ とする。$x,y$ は $v_i$ より後ろの $v_i$ の隣接頂点なので隣接する。$Z$ の長さは $4$ 以上なので $x,y$ は $Z$ の上で隣り合わず、辺 $xy$ は $Z$ の弦である(FG65 pp. 851–852 の議論)。
3 ⇒ 4. 頂点数についての帰納法で、木 $T$ と部分木の族を作る。$n=1$ なら 1 点の木でよい。$n\ge2$ のとき、$G-v_1$ は完全消去順序 $v_2,\dots,v_n$ をもつので、帰納法の仮定から木 $T'$ と部分木 $(T'_u)_{u\ne v_1}$ で $G-v_1$ を表すものがある。$N(v_1)$ が空でなければ、それはクリークなので部分木 $T'_u$($u\in N(v_1)$)はどの 2 つも交わり、lem-cg-helly により共通の頂点 $t$ がある。$N(v_1)$ が空なら $t$ を $T'$ の任意の頂点とする。$T'$ に新しい頂点 $t^\ast$ を $t$ に結んで加えた木を $T$ とし、
$$ T_{v_1}=\{t^\ast\},\qquad T_u=\begin{cases}T'_u\cup\{t^\ast\}&(u\in N(v_1)),\\ T'_u&(u\notin N(v_1),\ u\ne v_1)\end{cases} $$
とおく。$u\in N(v_1)$ なら $t\in T'_u$ なので $T_u$ は連結である。$T_{v_1}$ と交わるのは $N(v_1)$ の頂点の部分木だけである。$u,w\ne v_1$ について、$T_u\cap T_w$ が $t^\ast$ を含むのは $u,w\in N(v_1)$ のときだけで、そのとき $t\in T'_u\cap T'_w$ なので、$T_u\cap T_w\ne\emptyset$ は $T'_u\cap T'_w\ne\emptyset$ と同値である。よって $(T_v)$ は $G$ を表す。
4 ⇒ 3. 頂点数についての帰納法による。$G$ が木 $T$ の部分木 $(T_v)$ の交差グラフであるとする。$T$ の頂点 $r$ を 1 つ決めて根とし、$r$ からの距離を深さという。部分木 $T_v$ の中で深さが最小の頂点はただ 1 つである(2 つあれば、その間の道は $T_v$ に入り、途中に深さがより小さい頂点を通る)。これを $\mathrm{top}(v)$ とすると、$T_v$ の頂点はすべて $\mathrm{top}(v)$ の子孫である。$\mathrm{top}(v)$ の深さが最大の $v$ をとり、$v$ が単体的であることを示す。$u\in N(v)$ とし、$x\in T_u\cap T_v$ をとる。$\mathrm{top}(u)$ の深さは $\mathrm{top}(v)$ の深さ以下なので、$\mathrm{top}(u)=\mathrm{top}(v)$ であるか、$\mathrm{top}(u)$ は $\mathrm{top}(v)$ の子孫でない。後者のとき、$\mathrm{top}(v)$ の子孫である $x$ から $\mathrm{top}(u)$ への道は $\mathrm{top}(v)$ を通り、$T_u$ に含まれる。いずれにしても $\mathrm{top}(v)\in T_u$ である。よって $N(v)$ の頂点の部分木はすべて $\mathrm{top}(v)$ を含み、どの 2 つも交わるので $N(v)$ はクリークである。$G-v$ は部分木の族 $(T_u)_{u\ne v}$ の交差グラフなので、帰納法の仮定から完全消去順序をもち、その前に $v$ を置けばよい。$\square$

1 ⇔ 3 は Fulkerson–Gross が単体的頂点を順に消す判定法として述べた(FG65 §7, pp. 851–852)。1 ⇔ 4 は Gavril(1974)による。
条件 4 の表現は、木幅 の木分解と同じものである。部分木の族 $(T_v)$ から袋 $V_t=\{v\mid t\in T_v\}$ を作ると、各袋はクリークで、$(T,(V_t))$ は $G$ の木分解になる。逆に、どの袋もクリークである木分解から $T_v=\{t\mid v\in V_t\}$ とおくと、$G$ を表す部分木の族になる。こうして thm-cg-main は「$G$ が弦グラフであることと、どの袋もクリークである木分解をもつことは同値」も含む(Die25 Proposition 12.3.6, p. 369)。

完全消去順序に沿った計算

以下、$v_1,\dots,v_n$ を弦グラフ $G$ の完全消去順序とし、$V_i=\{v_i,\dots,v_n\}$、$C_i=N[v_i]\cap V_i$ とおく。$C_i$ は $v_i$ とその後ろの隣接頂点からなるクリークである。

極大クリークの列挙

$G$ の極大クリークはどれも $C_1,\dots,C_n$ のどれかに等しい。とくに弦グラフの極大クリークは $n$ 個以下で、$\omega(G)=\max_i|C_i|$ である。

極大クリーク $K$ の頂点で番号が最小のものを $v_i$ とすると、$K\subset N[v_i]\cap V_i=C_i$ である。$C_i$ はクリークなので、$K$ の極大性から $K=C_i$ である。$\square$

この列挙は FG65 p. 852 にある。一般のグラフでは極大クリークは指数個ありうる。ex-cg-counter の 3 の正八面体を $k$ 組の対に広げた完全 $k$ 部グラフ $K_{2,\dots,2}$ は、各対から 1 点ずつ選んだ $2^k$ 個の極大クリークを $2k$ 頂点でもつ。

彩色とクリーク被覆

弦グラフ $G$ について次が成り立つ。

  1. 頂点を $v_n,v_{n-1},\dots,v_1$ の順に、すでに色の付いた隣接頂点が使っていない最小の番号の色で塗ると、使う色は $\omega(G)$ 個以下である。したがって $\chi(G)=\omega(G)$ である。
  2. 残っている頂点のうち番号が最小のもの $v$ を選び、$v$ と残っている隣接頂点を取り除く、という操作を頂点がなくなるまで繰り返す。選んだ頂点の集合 $I$ は最大の独立集合で、$\alpha(G)=|I|=\theta(G)$ である。
後ろの隣接頂点はクリークをなす

1. $v_i$ を塗るとき、色の付いた隣接頂点は $v_i$ より後ろの隣接頂点、すなわち $C_i\setminus\{v_i\}$ である。$C_i$ はクリークなので $|C_i|-1\le\omega(G)-1$ 個しかなく、色 $1,\dots,\omega(G)$ のどれかが空いている。クリークの頂点は相異なる色を要するので $\chi(G)\ge\omega(G)$ である。
2. $v=v_i$ を選ぶとき、残っている頂点はすべて番号が $i$ 以上なので、$v$ と残っている隣接頂点の集合 $D_v$ は $C_i$ に含まれ、クリークである。$v$ を選んだ後に残る頂点は $v$ に隣接しないので、$I$ は独立集合である。各頂点はちょうど 1 回取り除かれるので、$(D_v)_{v\in I}$ は $V$ を $|I|$ 個のクリークに分ける。独立集合はどのクリークとも高々 1 点で交わるので $\alpha(G)\le\theta(G)\le|I|\le\alpha(G)$ である。$\square$

弦グラフの誘導部分グラフは弦グラフなので、1 からすべての誘導部分グラフで $\chi=\omega$、すなわち弦グラフはパーフェクトである(Die25 Proposition 5.5.2, p. 140 は貼り合わせの構造から示している)。2 は補グラフ $\overline G$ のすべての誘導部分グラフで $\chi=\omega$ となることを与え、$\overline G$ もパーフェクトである。これは パーフェクトグラフ定理 の、弦グラフの場合の直接の証明になっている。
単体的頂点かどうかは隣接頂点の対を調べれば確かめられるので、単体的頂点を探して取り除くことを繰り返すと、多項式時間で弦グラフかどうかを判定し、完全消去順序を求められる(この判定の手順は FG65 p. 851 による)。prop-cg-cliques と prop-cg-coloring により、弦グラフでは最大クリーク・彩色数・最大独立集合も多項式時間で求まる。一般のグラフではこれらを求める問題は NP完全問題 の典型である。

完全消去順序の計算

頂点 $1,\dots,6$ と辺 $12,13,23,24,34,35,45,46,56$ のグラフ(三角形を 4 つ帯状に並べたもの)を考える。$1$ の隣接頂点 $2,3$ は隣接するので $1$ は単体的である。$1$ を除くと $2$(隣接頂点 $3,4$)、続いて $3$($4,5$)、$4$($5,6$)が単体的になり、$1,2,3,4,5,6$ は完全消去順序である。$C_1=\{1,2,3\}$、$C_2=\{2,3,4\}$、$C_3=\{3,4,5\}$、$C_4=\{4,5,6\}$、$C_5=\{5,6\}$、$C_6=\{6\}$ で、極大クリークは前の 4 つ、$\omega=3$ である。$6,5,\dots,1$ の順に塗ると $6\mapsto1$、$5\mapsto2$、$4\mapsto3$、$3\mapsto1$、$2\mapsto2$、$1\mapsto3$ で $3$ 色である。番号の順に独立集合を選ぶと $1$($2,3$ を除く)、$4$($5,6$ を除く)で、$\alpha=2$、クリーク被覆は $\{1,2,3\},\{4,5,6\}$ である。部分木による表現は、道 $t_1-t_2-t_3-t_4$ の上で $T_1=\{t_1\}$、$T_2=\{t_1,t_2\}$、$T_3=\{t_1,t_2,t_3\}$、$T_4=\{t_2,t_3,t_4\}$、$T_5=\{t_3,t_4\}$、$T_6=\{t_4\}$ とすればよい($t_i$ が $C_i$ に当たる)。

例と反例

反例
  1. $C_4$. 頂点 $1,2,3,4$ の閉路は弦グラフでない。どの頂点の 2 つの隣接頂点も隣接しないので単体的頂点がなく、$\{2,4\}$ は $1$ と $3$ の極小分離集合だがクリークでない。一方 $C_4$ は二部グラフなので $\chi=\omega=2$ で、パーフェクトである。
  2. $C_4$ に葉を付けたもの. $C_4$ の頂点 $1$ に頂点 $5$ を結ぶと、$5$ は単体的だが、グラフは弦グラフでない。$5$ を除くと単体的頂点がなくなり、完全消去順序は作れない。
  3. 正八面体のグラフ $K_{2,2,2}$($6$ 頂点を 3 組の対に分け、同じ対に入らない 2 頂点を結ぶ)は、各対から 1 点ずつ選んだ $2^3=8$ 個の三角形を極大クリークにもち、$8>6$ である。対 $\{a,a'\}$ と別の 2 対の頂点 $b,c,b',c'$ について $b,c,b',c'$ は $C_4$ をなすので、弦グラフでない。
  4. 塗る向き. 道 $a-b-c-d$ で $a,d,b,c$ は完全消去順序である。これを前から貪欲に塗ると $a\mapsto1$、$d\mapsto1$、$b\mapsto2$、$c\mapsto3$ となり、$\omega=2$ を超える。後ろから塗ると $c\mapsto1$、$b\mapsto2$、$d\mapsto2$、$a\mapsto1$ で 2 色である。
主張反例外れること
単体的頂点があれば弦グラフex-cg-counter の 2誘導部分グラフでも単体的頂点が見つかり続けること
パーフェクトなら弦グラフ$C_4$(ex-cg-counter の 1)長さ $4$ の誘導された閉路がないこと
極大クリークは頂点数以下正八面体(ex-cg-counter の 3)弦グラフであること
完全消去順序の前から塗ってもクリーク数の色で足りる道 $a-b-c-d$(ex-cg-counter の 4)後ろから塗ること
円周の弧の交差グラフは弦グラフ4 つの弧で表した $C_4$部分木の Helly 性(lem-cg-helly)

最後の行では、円周を 4 等分する弧 $[0,1],[1,2],[2,3],[3,0]$ は隣り合う弧どうしだけが交わり、交差グラフは $C_4$ である。円周の弧の族では、どの 2 つも交わっても全体に共通の点があるとは限らない(3 等分の弧 3 つが例である)。

関連項目

参考文献

[1]
Reinhard Diestel, Graph Theory, Springer, 2025, §5.5:弦グラフの定義と Propositions 5.5.1–5.5.2(p. 140)、§12.3:Proposition 12.3.6(p. 369)
[2]
D. R. Fulkerson; O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics 15 (1965), no. 3, 835–855, 1965, §7(pp. 851–853)。単体的頂点の消去による判定(pp. 851–852)、極大クリークの列挙(p. 852)

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