グラフに対する各種操作

グラフに対する操作としては, 辺を潰すのと取り除くのが基本である。 それによりあるグラフが別のグラフの minor である, という概念が定義できる。 Robertson と Seymour により一連の論文 ([RS83]から [RS04]) の中で調べられている。

• contraction
• deletion
• minor

Minorを取る操作で閉じたグラフの類を考えるときには“forbidden minor”に よる特徴付けを考える。例えば, 平面グラフを特徴づけるKuratowskiの定理と か, 多面体のグラフに関するSteinitzの定理 などがある。RobertsonとSeymourの仕事は, その一般化と考えられる。 RobertsonとSeymourの仕事の解説として, Lovászの[Lov06]があ る。またこれらの一般化をMelikhovが[Mel]で考えている。

Capraso [Cap] は, contractionだけを考えてそれをグラフの間の 同値関係に拡張したものをlinkedと呼んでいる。その論文の目的は tropical curveのmoduli spaceを 調べることであるが。

Category theoryの視点からは, product, coproduct, そしてexponential graph (Hom graph)が考えられる。これらについては, Dochtermannの[Doc09]を見るとよい。

• product
• coproduct
• exponential graph (Hom graph)

Hajiabolhassan と Taherkhani [HT]はgraphの fractional powersを考えている。

他に目についた操作として次のようなものがある。

• \(n\)-coneあるいはgeneralized Mycielski construction ([Tar01; DS12])
• whiskeringやclique-whiskering ([Vil90; IN])
• \(N\)-flip ([NSS06])
• blow-up ([HHN])
• corona ([FH70; MM])

Independence complex を通して, wiskeringに対応する simplicial complexに対する操 作も考えられている。Biermannとvan Tuylの [BT]やFrohmaderの [Fro]である。

References

[BT]

Jennifer Biermann and Adam Van Tuyl. Balanced vertex decomposable simplicial complexes and their \(h\)-vectors. arXiv: 1202.0044.

[Cap]

Lucia Caporaso. Geometry of tropical moduli spaces and linkage of graphs. arXiv: 1001.2815.

[Doc09]

Anton Dochtermann. “Hom complexes and homotopy theory in the category of graphs”. In: European J. Combin. 30.2 (2009), pp. 490–509. arXiv: math/0605275. url: http://dx.doi.org/10.1016/j.ejc.2008.04.009.

[DS12]

Anton Dochtermann and Carsten Schultz. “Topology of Hom complexes and test graphs for bounding chromatic number”. In: Israel J. Math. 187 (2012), pp. 371–417. arXiv: 0907.5079. url: http://dx.doi.org/10.1007/s11856-011-0085-6.

[FH70]

Roberto Frucht and Frank Harary. “On the corona of two graphs”. In: Aequationes Math. 4 (1970), pp. 322–325.

[Fro]

Andrew Frohmader. How to construct a flag complex with a given face vector. arXiv: 1112.6061.

[HHN]

Hamed Hatami, James Hirst, and Serguei Norine. The inducibility of blow-up graphs. arXiv: 1108.5699.

[HT]

Hossein Hajiabolhassan and Ali Taherkhani. Graph Powers and Graph Homomorphisms. arXiv: 0808.0362.

[IN]

David Cook II and Uwe Nagel. Cohen-Macaulay graphs and face vectors of flag complexes. arXiv: 1003.4447.

[Lov06]

László Lovász. “Graph minor theory”. In: Bull. Amer. Math. Soc. (N.S.) 43.1 (2006), 75–86 (electronic). url: http://dx.doi.org/10.1090/S0273-0979-05-01088-8.

[Mel]

Sergey A. Melikhov. Combinatorics of embeddings. arXiv: 1103.5457.

[MM]

Cam McLeman and Erin McNicholas. Spectra of Coronae. arXiv: 1111.1200.

[NSS06]

Atsuhiro Nakamoto, Tadashi Sakuma, and Yusuke Suzuki. “\(N\)-flips in even triangulations on the sphere”. In: J. Graph Theory 51.3 (2006), pp. 260–268. url: http://dx.doi.org/10.1002/jgt.20132.

[RS04]

Neil Robertson and P. D. Seymour. “Graph minors. XX. Wagner’s conjecture”. In: J. Combin. Theory Ser. B 92.2 (2004), pp. 325–357. url: http://dx.doi.org/10.1016/j.jctb.2004.08.001.

[RS83]

Neil Robertson and P. D. Seymour. “Graph minors. I. Excluding a forest”. In: J. Combin. Theory Ser. B 35.1 (1983), pp. 39–61. url: http://dx.doi.org/10.1016/0095-8956(83)90079-5.

[Tar01]

Claude Tardif. “Fractional chromatic numbers of cones over graphs”. In: J. Graph Theory 38.2 (2001), pp. 87–94. url: http://dx.doi.org/10.1002/jgt.1025.

[Vil90]

Rafael H. Villarreal. “Cohen-Macaulay graphs”. In: Manuscripta Math. 66.3 (1990), pp. 277–293. url: https://doi.org/10.1007/BF02568497.