数理解析研究所講究録
1531 巻 2007 年 108-112

108

The box complexes of graphs without 3 and 4-cycles
筑波大学数理物質科学研究科

上別府陽 (Akira Kamibeppu)

Institute of Mathematics, University of Tsukuba
有限集合 $V$ (頂点集合) と $V$ の二元部分集合からなる族 $E$ (辺集合) との組 $G=(V, E)$ をgraph という. $V(G),$ $E(G)$ でそれぞれ, graph $G$ の頂点集合, 辺集合を表すことにする. この定義からわかるように, graph は多重辺やループを含まない. 以下では孤立点を持たない graph を考える. graph $G$ の -彩色 ( -coloring) とは, $\{u, v\}\in E(G)$ ならば $f(u)\neq f(v)$ を満たす写像$f:V(G)arrow\{1, \cdots, k\}$ のことをいう. このとき, 自然数
$k$

$k$

$\chi(G):=\min${$k\in \mathrm{N}|G$は k-彩色を持つ}を gaph $G$ の彩色数 (chromatic number) という. $\chi(G)$ の下界を与える方法の 1 つとして, graphの box complex と呼ばれる単体的複体$G$いる. まずを$\mathrm{B}(G)$の位相幾何学的な情報を用いる方法が知られての定義を与え, その方法を紹介するための準備をする.
$\mathrm{B}(G)$$G$

を graph とし, $A\subseteq V(G)$ とする どの $a\in A$ に対して$A$のcommon neighbor と呼ぶ.

便宜上,$\mathrm{C}\mathrm{N}_{G}(\phi)=V(G)$$A$の$\text{も},$$\{v, a\}\in E(G)$ である $V\in V(G)$common neighbor 全体からなる集合をと定義する. $A=\{u\}$ のとき,$\mathrm{C}\mathrm{N}_{G}(A)$$\mathrm{C}\mathrm{N}_{G}(A)$で表す.

は $G$ における $u\in V(G)$ のneighbor 全体からなる集合であることがわかる.
$A_{1},$$A_{2}\subseteq V(G),$ $A_{1}\cap A_{2}=\phi$に対して,$V=A_{1}\cup A_{2},$ $E=\{\{a_{1},a_{2}\}|a_{1}\in A_{1}, a_{2}\in A_{2}, \{a_{1}, a_{2}\}\in E(G)\}$で定義されるとは, 任意の$\mathrm{G}$の bipa tite subgraph $(\mathrm{V}, E)$ を $G[A_{l}, A_{\mathit{2}}]$ で表す. $G[A_{1}, \mathrm{A}_{2}]$ が complete である$(a_{1}, a_{2})\in A_{1}\mathrm{x}A_{2}$に対し,$\{a_{1},a_{\mathit{2}}\}\in E(G)$と $G[A_{1}, \phi]$ も complete であると呼ぶことにする.

が成立することをいう. 便宜上, $G[\phi,A_{2}]$$A_{2}\subseteq V(G)$$A_{1},$

に対し,$A_{1}\omega A_{2}:=(A_{1}\cross\{1\})\cup(A_{2}\cross\{2\})(\subseteq V(G)\cross\{1,2\})$と定義する.

graph

$G$

に対して, $V(G)\cross\{1,2\}$ の部分集合族$\mathrm{B}(G)=\{A_{1}\mathfrak{G}A_{2}|A_{1},A_{\mathit{2}}\subseteq V(G),$$A_{1}\cap A_{2}=\phi$$G[A_{1}, A_{2}]$,: complete,$\mathrm{C}\mathrm{N}_{G}(A_{1})\neq\phi\neq \mathrm{C}\mathrm{N}_{G}(A_{2})\}$

で与えられる抽象単体的複体を $G$ の box complex という.
$X$ を位相空間とし,を満たす同相写像 : $Xarrow X$ を $X$ 上の -action と呼び, 位相は不動点を持たない -action
空間と-action との対 (X, ) を -space と呼ぶ. 多面体-space になる : 任意のとして, 次で定義される simplicial map の afliine extention を持ち,$\nu\circ\nu=\mathrm{i}\mathrm{d}_{X}$$\mathbb{Z}_{2}$$\nu$$\mathbb{Z}_{2}$$\nu$$||\mathrm{B}(G)||$$\mathbb{Z}_{2}$$\nu$$\mathbb{Z}_{2}$$\mathbb{Z}_{2}$$v\in V(G)$ に対して,$\nu:V(\mathrm{B}(G))arrow V(\mathrm{B}(G))$;$\{v\}\mathrm{U}+\emptyset\ovalbox{\tt\small REJECT}\mapsto\emptyset\oplus\{v\},$$\emptyset\oplus\{v\}\vdasharrow\{v\}W\phi$.

109
このとき, 多面体
2 つのものを$\mathbb{Z}_{2^{-}}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{c}\mathrm{e}$

$X$

から$Y$

-action に関して$(X, \nu_{X})$ と (, 取) の間の連続写像 :$||\mathrm{B}(G)||$へ拡張された$Y$への$\mathbb{Z}_{2^{-}}\mathrm{m}\mathrm{a}\mathrm{p}$と呼ぶ. 以下では,$\mathbb{Z}_{2}$$\nu$$\mathbb{Z}_{2}${$k|\mathbb{Z}_{2}$-map$\mathbb{Z}_{2}$$f$の$\mathbb{Z}_{2}$-index が定義できる.

で, 咋 $\circ f=f\circ\nu_{X}$ を満たす

-action は常に antipodal-index は次で定義される :次元球面-space(X, ) の$\mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(X, \nu):=\min$の下界は, box complex の$k$$||\mathrm{B}(G)||$$Xarrow \mathrm{Y}$$f$map を考えることにする 一般に,$\chi(G)$$\mathbb{Z}_{2}$$S^{k}$

上の$\mathbb{Z}_{2}$: $Xarrow S^{k}$ が存在}.

-index で与えられることが知られている.

Theorem 1 (J. Matou\v{s}ek-G. M. Ziegler [4]: p.125). 任意の graph$\chi(G)\geq \mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\mathrm{B}(G)||)+2$

$G$

に対して,

.

このような研究は, graph の彩色数に関する Kneser 予想 ([4],を参照) が位相幾何学を応用して証明されたことから始まる ([3], [6] を参照).-方で graph $G$ が与えられたとき, box
complexの位相を上の定義から直接知ることは (complete graph など特別なものを除いて) 難しい. 以下では,が持つ幾何学的な特徴に注目して得られた結果を述べる.
$\mathrm{p}.57$$||\mathrm{B}(G)||$$||\mathrm{B}(G)||$connected graph$||\mathrm{B}(\mathrm{G})||$$G$はその sprning tree $T$ にいくつかの辺を加えて表すことができるからの位相を調べるために, 次の 2 つの目標をたてることができる :tree の box complex の位相を調べる.
graph$G$のspanning tree

$T$をとり,$\mathrm{B}(G)$を$\mathrm{B}(T)$を用いて表す.

(I) tree の box complex の位相について :とする.

$f1(X)=A,$であって, 任意の $t\in[0,1]$ に対して,$Xarrow X$ がであるような homotopy $\{f_{1} : Xarrow X\}$ が存在するとき, $A$ を $X$ のdeformation retract という.
$A\subset X$$f\mathrm{o}=\mathrm{i}\mathrm{d}_{X},$$f_{t}|_{A}=\mathrm{i}\mathrm{d}_{A}$$\mathbb{Z}_{2^{-}}\mathrm{m}\mathrm{a}\mathrm{p}$$f_{t}$:$\mathbb{Z}_{2^{-}}$

は2つを tree とする. tree の box complex
Theorem 2(tree の box complex).の四四な component からなる. さらに を 1 次元 simplicial complex と見なして,の各のcomponent へ埋め込むことができ, その像は-deformation retract である.
$T$

$T$

$||\mathrm{B}(T)||$$T$$||\mathrm{B}(T)||$$||\mathrm{B}(T)||$$\mathbb{Z}_{2}$

これを示すためには, 次の 2 つの定理を用いる.

Theorem 3(box complex の分解定理). graph$G$の subgraph $G_{1)}\cdots$)$G_{k}$

が $G= \bigcup_{1=1}^{k}.G_{i}$ を満たし, 更に次の条件$G[M_{1}, M_{\mathit{2}}]$が complete であるような任意の極大部分集合$M_{1}$

田 $M_{\mathit{2}}\subseteq V(G)\cross\{1,2\}$に対して, $G_{i}[M_{1}, M_{2}]$ が complete であるような $i\in\{1, \cdots, k\}$ が存在するを満たすとする. そのとき,$G$の頂点 $v\in V(G)$ で$A\subseteq V(G)$$v$$\mathrm{B}(G)=\bigcup_{1=1}^{k}.\mathrm{B}(c_{:})$

が成り立つ.の neighbor が唯–つしかないとき, $v$ を $G$ の端点という. 部分集合のどの 2 点も $G$ の辺で結べないとき, $A$ は $G$ で独立 (independent) であるという.

Theorem 4(貼り合わせ定理 1).て G\cap H が

2 つの graph $G$ と $H$ の和で表せる graph $G\cup H$ におい110$V(G\cap H)=\{u_{1}, \cdots, u_{k}, v_{1}, \cdots, v_{k}\},$$E(G\cap H)=\{\{u_{i}, v_{i}\}|i=1, \cdots, k\}$と表されていて, 次の条件を満たすとする :(1) $\{u_{i}, v_{j}\}\not\in E(G\cup H)(i\neq i)$ ,は(3)の端点,$v_{1},$$\cdots,$

(2)
(4)

$G$

$v_{k}$$u_{1},$$\cdots,$ $u_{k}$は $H$ の端点,$\{u_{1}, \cdots, u_{k}\}$は $G$ で独立.

このとき, $\mathrm{B}(G\cup H)=\mathrm{B}(G)\cup \mathrm{B}(H),$ $\mathrm{B}(G\cap H)=\mathrm{B}(G)\cap \mathrm{B}(H)$ が成り立つ.
$G\cup H$

$G$

$H$

(I) graph の sprning troe をとり,をを用いて表す :を connected graph で rank $H_{1}(G)=k$ であるとする.の spanning treeと $E(T)\cup$$\{e_{1}, \cdots, e_{k}\}=E(G)$ を満たす個の辺をとり, この番号順に に辺を加えることを考える. 即ち $G_{0}=T$ とし, 各をに対して, graph
$G$

$T$

$\mathrm{B}(G)$$\mathrm{B}(T)$

$G$

$G$

$k$

$\mathrm{i}=1,$$e_{1},$$\cdots,$

$T$

$T$

$\cdots,$ $e_{k}$$k$$c_{:}$$V(c_{:})=V(T)(=V(G)),$ $E(c_{:})=E(T)\cup\{e_{1}, \cdots, e_{1}\}$と定義する. また, graph$G_{\epsilon_{i}}$を次のように定義する :$V(G_{e_{1}})=\{u_{i},v_{i}\}\cup \mathrm{C}\mathrm{N}_{G_{i-1}}(u_{i})\cup \mathrm{C}\mathrm{N}c_{:-1}(v:)$,$E(G_{e_{1}})=\{\{u_{i},x\}|x\in \mathrm{C}\mathrm{N}_{c_{:-1}}(u_{i})\}\cup\{\{v_{1},y\}|y\in \mathrm{C}\mathrm{N}_{c_{:-1}}(v_{1})\}\cup\{e_{i}\}$$\mathrm{C}\mathrm{N}_{G:-1}(\{u_{i}, v_{i}\})=\emptyset$のとき, graph$G_{\text{。}}$.

‘は tree になることがわかる.

$G_{i-1}$$G_{\mathrm{e}}$:このとき, $G_{i}=G_{i-1} \cup G_{e_{i}}=\cdots=T\cup\bigcup_{j=1}^{i}G_{\epsilon_{j}}$ である. $G$ が長さが 4 以下の cycle を含まない
とき, 次の結果を得る.

Theorem 5.
に対し,
graph
$T$

$e_{1},$$G_{i-1}$と$G$を長さが 4 以下の cycle を含まない connected graph とする. $G$ の spanning tree$\cdots,$ $e_{k}1\mathrm{h}E(G)\backslash E(T)=\{e_{1}, \cdots, e_{k}\}$$G_{\epsilon_{1}}$を満たす$k$個の辺とする. 上で定義したの和で表される graph $G_{1}=G_{i-1}\cup G_{e:}$ と各 $i=1,$$\cdots,$

$k$

に対し,

111
$\mathrm{B}(G_{i-1}\cup G_{e:})=\mathrm{B}(G_{i-1})\cup \mathrm{B}(G_{e_{i}}),$

が成り立つ. したがって,$\mathrm{B}(G_{i-1}\cap G_{e}.)=\mathrm{B}(G_{i-1})\cap \mathrm{B}(G_{e})$:: が成り立つ.

$\mathrm{B}(G)=\mathrm{B}(T)\cup\bigcup_{i=1}^{k}\mathrm{B}(G_{\text{。}})$

このことは, 次の定理を用いて得られる.

Theorem 6(貼り合わせ定理 2). graph $H$ は頂点集合が$V(H)=\{u_{1}, \cdots \dagger u_{k}, u, v_{1}, \cdots, v_{l}, v\}$

,辺集合が$E(H)=\{\{u, u_{i}\}|i=1, \cdots, k\}\cup\{\{v, v_{j}\}|j=1, \cdots,l\}\cup\{\{u, v\}\}$で定義された tree とする. 2 つの gaph $G$ と $H$ の和で表せる graph $G\cup H$ において, 2 つのgraph$G$と $H$ の共通部分が$V(G\cap H)=\{u_{1}, \cdots,u_{k},u,v_{1}, \cdots,v_{l}, v\},$ $E(G\cap H)=E(H)\backslash \{\{u, v\}\}$と表されていて, 次の (1) $\sim(3)$ を満たすとする :
(1)
,
(2)
,
(3)
independent.
$\mathrm{C}\mathrm{N}_{G}(u)=\{u_{1}, \cdots, u_{k}\}(=\mathrm{C}\mathrm{N}_{H}(u)\backslash \{v\})$$\mathrm{C}\mathrm{N}_{G}(v)=\{v_{1}, \cdots, v_{l}\}(=\mathrm{C}\mathrm{N}_{H}(v)\backslash \{u\})$$\{u_{1}, \cdots, u_{k}, v_{1}, \cdots, v_{l}\}[]\mathrm{h}G^{-}C$

このとき, $\mathrm{B}(G\cup H)=\mathrm{B}(G)\cup \mathrm{B}(H),$以上のことから$\mathrm{B}(G)$を$\mathrm{B}(T)$$\mathrm{B}(G\cap H)=\mathrm{B}(G)\cap \mathrm{B}(H)$が成り立つ.と $\mathrm{B}(G_{e}):(i=1, \cdots, k)$ の和で表すことができた. graph $G$ が長さ 4 以下の cycle を持たなければは tree だから
は 2 つの可縮な component からなる. 上の結果を用いての位相を次のようにして調べることができる.
を次で定義さ$||\mathrm{B}(G_{e_{1}})||$$G_{\text{。_{}i}}$$||\mathrm{B}(G)||$れる$\mathrm{B}(G)$$\overline{G}$の 1 次元 simplicial subcomplex とする:$\overline{G}:=\{\{u\}\oplus\emptyset, \{v\}.\cup+\phi, \phi\oplus\{u\}, \phi\oplus\{v\}, \{u\}\oplus\{v\}, \{v\}\mathrm{B}\{u\}|\{u,v\}\in E(G)\}\subset \mathrm{B}(G)$$||\mathrm{B}(G)||$上の$\mathbb{Z}_{2^{-}}\mathrm{a}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$Theorem 7.
$||\mathrm{B}(G)||$$||\overline{G}||$の$\mathbb{Z}_{2}$を$||\overline{G}||$へ制限することで,$||\overline{G}||$上の$\mathbb{Z}_{2}$-action が得られる.

を長さが 4 以下の cycle を含まない connected graph とする. このとき,-deformation retract である.
$G$$||\overline{G}||$はの homotopy type は次のようになる.

Theorem 8.

$G$を conected graph とし, rank $H_{1}(G)=k$ であるとする. このとき,$||\overline{G}||$について次が成り立つ.
(1) $G$ に含まれる cycle は, すべて偶数の長さを持つならば,$|| \overline{G}||\simeq S^{1}\Pi\bigvee_{k}^{s^{1}}k$ ’

(2)

$G$

は長さが奇数の cycle を少なくとも 1 つ含むなら,$||\overline{G}||\simeq s^{1}2k-1^{\cdot}$$G$が長さが 4 以下の cycle を含まない connected graph の場合, 上記の Thmrem 7 と 8 から$||\mathrm{B}(G)||$の homotopy type が決定できる.

112
Corollary 9.

を長さが 4 以下の cycle を含まない connected graph とし, rank $H_{1}(G)=k$ であるとする. このとき, box complexについて次が成り立つ.
(1) $G$ に含まれる cycle は, すべて偶数の長さを持つならば,$G$$||\mathrm{B}(G)||$$|| \mathrm{B}(G)||\simeq\bigvee_{k}S^{1}$

(2)

$G$

垣$\vee^{s^{1}}k$’は長さが奇数の cycle を少なくとも 1 つ含むなら,$||\mathrm{B}(G)||\simeq s^{1}\mathit{2}k-1^{\cdot}$

さて, 長さが 4 以下の cycle を含まない connected graph $G$ に対し, Theorem 7 からへのら-map があることがわかる. このとき, -index の定義から,$||\overline{G}||$$||\mathrm{B}(G)||$か$\mathbb{Z}_{2}$$\mathbb{Z}_{\mathit{2}}$$\mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\mathrm{B}(G)||)\leq \mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\overline{G}||)$

である. また$\overline{G}$

点を持たないの定義から,$\mathbb{Z}_{\mathit{2}}$$||\mathrm{B}(G)||$-action を与える.

$\overline{G}$-action を上に制限したものは,が 1 次元 simplicial complex であることから,上の$\mathbb{Z}_{2}$$||\overline{G}||$$||\partial||$上に不動$\mathrm{i}\mathrm{n}\mathrm{d}_{l_{2}}(||\mathrm{B}(G)||)\leq \mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\overline{G}||)\leq 1$が成り立つ.
を得る. したがって,方, Erd\"os の定理 ([1], p.117) により, 任意の正の整数$\mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\mathrm{B}(G)||)+2\leq 3$に対して, 長さが 以下の cycle を含まず, $\chi(G)>k$ であるような graph が存在するから, 一般に Theorem 1 で述べた graph の彩と graph $G$ の彩色数 $\chi(G)$ との差はいくらでも大きくなりうる
色数の下界
$k$

$k$

$\mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\mathrm{B}(G)||)+2$

ことがわかる.

既に, J. W. Walker [7], \S 12 によって, 長さが 4 以下の cycle を含まない graph の彩色数の下界を位相的に評価する L. Loviz 等による既存の方法には限界があると指摘されている.2002
年, J. Matou\v{s}ek, G. M. Ziegler [5] によって, 長さが 4 以下の cycle を含まない graph で, $\chi(G)$ との差がいくらでも大きくなりうることが指摘されている. 更に 2004 年に
P. Csorba [2] はこのような graph のもう –つの例を与えている.

$\mathrm{i}\mathrm{n}\mathrm{d}_{\mathrm{Z}_{2}}(||\mathrm{B}(G)||)+2$

参考文献[1] R. Diestel, Graph Theory. 3rd ed. Graduate Texts in Mathematics 173, Springer-Verlag, 2005.
[2] P. Csorba. Homotopy types of box complex,$\mathrm{a}\mathrm{r}\mathrm{X}\mathrm{i}\mathrm{v}:\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}.\mathrm{C}\mathrm{O}/0406118\mathrm{v}\mathrm{l}$, 2004.

[3] L. Lov\’asz. Kneser’s conjecture, chromatic number and homotopy. J.Combinatorial Theory, Ser.
$\mathrm{A}$, 25:319-324, 1978.

[4] J. Matou\v{s}ek. Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry, Universitext, Springer-Verlag, 2003.
[5] J. Matougek and G. M. Ziegler. Topological lower bounds for the chromatic number: A hierarchy.
, 2002.
Manuscript,$\mathrm{a}\mathrm{r}\mathrm{X}\mathrm{i}\mathrm{v}:\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{h}.\mathrm{C}\mathrm{O}/0208072$[6] K. S. Sarkaria. A generalized Kneser conjecture. J.Combinatorial Theory, Ser. , 49:236-240, 1990.
$\mathrm{B}$[7] J. W. Walker. From graphs to ortholattices to equivariant maps. J. Combinatorial Theory, Ser. ,35:171-192, 1983.
$\mathrm{B}$