グラフの色付けに関する不変量

グラフの不変量として最も有名なものの一つは, chromatic number だろう。

• グラフ \(G\) の chromatic number \(\chi (G)\)

Chromatic number というのは, graph の頂点の塗り分け問題から派生した graph の不変量で, 有名な四色問題も graph の chromatic number に関する問題である。 Hadwiger 予想というより一般的な予想もある。

• 四色問題
• Hadwiger 予想

Leinster の この\(n\)-Category Caféのpost によると, \[ \chi (G\times H) = \min \{\chi (G),\chi (H)\} \] が成り立つという予想は, Hedetniemi 予想と呼ばれているようである。 Shitov [Shi19] により反例が発見されている。これについては, Kalai の blog post に解説がある。 より小さな反例は, Zhu の [Zhu] にある。

Chromatic number を調べるのに rational homotopy theory を使うというアイデアもある。Lechuga と Murillo の [LM00; LM01] など。

Chromatic number の変種も色々考えられている。

• quantum chromatic number [Cam+]
• circular chromatic number
• \(b\)-chromatic number
• fractionalcut-covering number と cubical chromatic number [Šám]
• 有限群に値を持つ chromatic number [BB]
• game chromatic number [KS]

Ma と Cai の [MC] によると, circular chromatic number は, Vince により [Vin88] で star chromatic number という名前で定義されたらしい。 \(b\)-chromatic number は, Irving と Manlove により [IM99] で定義された。Hajiabolhassan [Haj] や Javadi と Omoomi [JO09] により, Kneser graph の場合が調べられている。 \(b\)-chromatic number に関し, グラフが \(b\)-continuous である, という性質も定義されている。Shaebani の [Sha] など。

グラフ全体ではなく, ある頂点に隣接した頂点を集めた部分グラフの chromatic number を考えると, local chromatic number という数が定義される。

• local chromatic number

Mohar, Simonyi, Tardos の [MST] によると, [Erd+86] で定義されたらしい。 また [ST06; STV09] を参照するよう書いてある。

距離空間 \((X,d)\) と \(\delta >0\) に対し, \(X\) の点を頂点とし, 距離が丁度 \(\delta \) だけ離れた点を辺で結ぶことにより graph ができる。この graph の chromatic number を, 距離空間 \((X,d)\) の chromatic number というらしい。

• 距離空間の chromatic number

例えば, Raigorodskii の [Rai] や Parlier と Petit の [PP] で調べられている。

色の数 \(t\) を決めたとき, グラフ \(G\) の頂点を \(t\) 色に塗り分ける方法の数は \(t\) に関する多項式になり, \(G\) の chromatic polynomial と呼ばれる。 その変種も色々考えられている。

• グラフの多項式不変量

Yoshinaga [Yos] は chromatic functor という不変量を導入した。 \(G\) を単純グラフとしたとき, 集合 \(X\) に対し \(G\) の \(X\)-coloring の集合を対応させる, 集合と単射の成す圏から自分自身への関手のことである。

• chromatic functor

Yoshinaga は, 2つの有限グラフが同じ chromatic polynomial を持つための必要十分条件は chromatic functor が同型であることを示している。

Liu [Liu] は, chromatic functor の automorphism group を調べている。また, 有限集合に限定すると 有限集合と単射の成す圏, つまり \(\category{FI}\) から自分自身への関手になるが, その性質につ いても調べている。

References

[BB]

Eric Babson and Matthias Beck. Counting Group Valued Graph Colorings. arXiv: 1204.1283.

[Cam+]

Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph. arXiv: quant-ph/0608016.

[Erd+86]

P. Erdős et al. “Coloring graphs with locally few colors”. In: Discrete Math. 59.1-2 (1986), pp. 21–34. url: http://dx.doi.org/10.1016/0012-365X(86)90065-8.

[Haj]

Hossein Hajiabolhassan. On the b-chromatic number of Kneser Graphs. arXiv: 0904.3977.

[IM99]

Robert W. Irving and David F. Manlove. “The \(b\)-chromatic number of a graph”. In: Discrete Appl. Math. 91.1-3 (1999), pp. 127–141. url: http://dx.doi.org/10.1016/S0166-218X(98)00146-2.

[JO09]

Ramin Javadi and Behnaz Omoomi. “On \(b\)-coloring of the Kneser graphs”. In: Discrete Math. 309.13 (2009), pp. 4399–4408. url: http://dx.doi.org/10.1016/j.disc.2009.01.017.

[KS]

Ralph Keusch and Angelika Steger. The game chromatic number of dense random graphs. arXiv: 1406.7126.

[Liu]

Ye Liu. On chromatic functors and stable partitions of graphs. arXiv: 1603.08310.

[LM00]

Luis Lechuga and Aniceto Murillo. “Complexity in rational homotopy”. In: Topology 39.1 (2000), pp. 89–94. url: http://dx.doi.org/10.1016/S0040-9383(98)00059-7.

[LM01]

Luis Lechuga and Aniceto Murillo. “The fundamental class of a rational space, the graph coloring problem and other classical decision problems”. In: Bull. Belg. Math. Soc. Simon Stevin 8.3 (2001), pp. 451–467. url: http://projecteuclid.org/euclid.bbms/1102714569.

[MC]

Zuqiang Ma and Junliang Cai. The Circular Chromatic Number of the Mycielskian of \(M^t(K_n)\). arXiv: 0901.2259.

[MST]

Bojan Mohar, Gábor Simonyi, and Gábor Tardos. Local chromatic number of quadrangulations of surfaces. arXiv: 1010.0133.

[PP]

Hugo Parlier and Camille Petit. Chromatic numbers of hyperbolic surfaces. arXiv: 1411.3565.

[Rai]

Andrei Raigorodskii. On the chromatic numbers of spheres in \(\R ^n\). arXiv: 1010.0384.

[Šám]

Robert Šámal. Cubical coloring – fractional covering by cuts and semidefinite programming. arXiv: 0911.2589.

[Sha]

Saeed Shaebani. On \(b\)-continuity Of Kneser Graphs of type \(KG(2k+1,k)\). arXiv: 0909.2770.

[Shi19]

Yaroslav Shitov. “Counterexamples to Hedetniemi’s conjecture”. In: Ann. of Math. (2) 190.2 (2019), pp. 663–667. arXiv: 1905.02167. url: https://doi.org/10.4007/annals.2019.190.2.6.

[ST06]

Gábor Simonyi and Gábor Tardos. “Local chromatic number, Ky Fan’s theorem and circular colorings”. In: Combinatorica 26.5 (2006), pp. 587–626. arXiv: math/0407075. url: https://doi.org/10.1007/s00493-006-0034-x.

[STV09]

Gábor Simonyi, Gábor Tardos, and Siniša T. Vrećica. “Local chromatic number and distinguishing the strength of topological obstructions”. In: Trans. Amer. Math. Soc. 361.2 (2009), pp. 889–908. arXiv: math/0502452. url: https://doi.org/10.1090/S0002-9947-08-04643-6.

[Vin88]

A. Vince. “Star chromatic number”. In: J. Graph Theory 12.4 (1988), pp. 551–559. url: http://dx.doi.org/10.1002/jgt.3190120411.

[Yos]

Masahiko Yoshinaga. Chromatic functors of graphs. arXiv: 1507.06587.

[Zhu]

Xuding Zhu. Relatively small counterexamples to Hedetniemi’s conjecture. arXiv: 2004.09028.