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

グラフの不変量として最も有名なものの一つは, 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 の [Zhu21] にある。

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

Chromatic number の変種も, 実に様々なものが考えられている。 目にしたものをまとめると次のようになる。

• \(b\)-chromatic number [IM99]
• fractionalcut-covering number と cubical chromatic number [Šám]
• 有限群に値を持つ chromatic number [BB]
• quantum chromatic number [Cam+]
• list chromatic number. [MŠ12]
• acyclic chromatic number. [MŠ12]
• acyclic list chromatic number. [MŠ12]
• degenerate chromatic number. [MŠ12]
• star chromatic number. [MŠ12]
• degenerate star chromatic number. [MŠ12]
• signed domination number [PZ].
• dynamic chromatic number [Ali11; AD].
• total chromatic number [Sha; JNS].
• locating chromatic number [BO11].
• fractional chromatic number [EK].
• distance chromatic number [KK69b; KK69a; KK08; MF].
• vector chromatic number
• oriented chromatic number [DS].
• \(r\)-dynamic chromatic number [Tah].
• distinguishing chromatic number [BP17].
• game chromatic number [KS].
• chromatic number of singed graphs [MRŠ].
• correspondence chromatic number [Ber16].
• packing chromatic number [Bre+17b; Bre+17a].
• circular chromatic number [AT18].
• injective chromatic number [MO].
• achromatic number [HHP67].
• pseudochromatic number [Gup69].
• dominated edge chromatic number [PA].
• achromatic number [HHP67].
• harmonious chromatic number [MP91; Ara+]
• acyclic \(b\)-chromatic number [ACP]

グラフ全体ではなく, ある頂点に隣接した頂点を集めた部分グラフの 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 の [PP16] で調べられている。

色の数 \(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

[ACP]

Marcin Anholcer, Sylwia Cichacz, and Iztok Peterin. On b-acyclic chromatic number of a graph. arXiv: 2206.06478.

[AD]

Arash Ahadi and Ali Dehghan. Upper Bounds for the Dynamic Chromatic Number of Graphs in Terms of the Independent Number. arXiv: 0911.4199.

[Ali11]

Meysam Alishahi. “On the dynamic coloring of graphs”. In: Discrete Appl. Math. 159.2-3 (2011), pp. 152–156. arXiv: 0908.2543. url: https://doi.org/10.1016/j.dam.2010.10.012.

[Ara+]

Gabriela Araujo-Pardo, Juan José Montellano-Ballesteros, Mika Olsen, and Christian Rubio-Montiel. On the harmonious chromatic number of graphs. arXiv: 2206.04822.

[AT18]

Meysam Alishahi and Ali Taherkhani. “Circular chromatic number of induced subgraphs of Kneser graphs”. In: Ars Math. Contemp. 15.1 (2018), pp. 161–172. arXiv: 1612.07462. url: https://doi.org/10.26493/1855-3974.1296.5c7.

[BB]

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

[Ber16]

Anton Bernshteyn. “The asymptotic behavior of the correspondence chromatic number”. In: Discrete Math. 339.11 (2016), pp. 2680–2692. arXiv: 1602.00347. url: https://doi.org/10.1016/j.disc.2016.05.012.

[BO11]

Ali Behtoei and Behnaz Omoomi. “On the locating chromatic number of Kneser graphs”. In: Discrete Appl. Math. 159.18 (2011), pp. 2214–2221. arXiv: 1104.3097. url: https://doi.org/10.1016/j.dam.2011.07.015.

[BP17]

Niranjan Balachandran and Sajith Padinhatteeri. “Distinguishing chromatic number of random Cayley graphs”. In: Discrete Math. 340.10 (2017), pp. 2447–2455. arXiv: 1406.5358. url: https://doi.org/10.1016/j.disc.2017.06.002.

[Bre+17a]

Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, and Kirsti Wash. “Packing chromatic number under local changes in a graph”. In: Discrete Math. 340.5 (2017), pp. 1110–1115. arXiv: 1608.05577. url: https://doi.org/10.1016/j.disc.2016.09.030.

[Bre+17b]

Boštjan Brešar, Sandi Klavžar, Douglas F. Rall, and Kirsti Wash. “Packing chromatic number, \((1,1,2,2)\)-colorings, and characterizing the Petersen graph”. In: Aequationes Math. 91.1 (2017), pp. 169–184. arXiv: 1608.05573. url: https://doi.org/10.1007/s00010-016-0461-8.

[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.

[DS]

Janusz Dybizbański and Andrzej Szepietowski. Oriented chromatic number of Halin graphs. arXiv: 1307.4901.

[EK]

Katherine Edwards and Andrew D. King. Bounding the fractional chromatic number of \(K_Δ\)-free graphs. arXiv: 1206.2384.

[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.

[Gup69]

Ram Prakash Gupta. “Bounds on the chromatic and achromatic numbers of complementary graphs”. In: Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968). Academic Press, New York, 1969, pp. 229–235.

[HHP67]

Frank Harary, Stephen Hedetniemi, and Geert Prins. “An interpolation theorem for graphical homomorphisms”. In: Portugal. Math. 26 (1967), pp. 453–462.

[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.

[JNS]

Geetha Jayabalan, Narayanan N, and K Somasundaram. Total Colourings - A survey. arXiv: 1812.05833.

[KK08]

Florica Kramer and Horst Kramer. “A survey on the distance-colouring of graphs”. In: Discrete Math. 308.2-3 (2008), pp. 422–426. url: http://dx.doi.org/10.1016/j.disc.2006.11.059.

[KK69a]

Florica Kramer and Horst Kramer. “Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz \(p\)”. In: Rev. Roumaine Math. Pures Appl. 14 (1969), pp. 1031–1038.

[KK69b]

Florica Kramer and Horst Kramer. “Un problème de coloration des sommets d’un graphe”. In: C. R. Acad. Sci. Paris Sér. A-B 268 (1969), A46–A48.

[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.

[MF]

Lian-Ying Miao and Yi-Zheng Fan. The Distance Coloring of Graphs. arXiv: 1212.1029.

[MO]

Mahsa Mozafari-Nia and Behnaz Omoomi. Injective chromatic number of outerplanar graphs. arXiv: 1706.02335.

[MP91]

Z. Miller and D. Pritikin. “The harmonious coloring number of a graph”. In: Discrete Math. 93.2-3 (1991), pp. 211–228. url: https://doi.org/10.1016/0012-365X(91)90257-3.

[MRŠ]

Edita Máčajová, André Raspaud, and Martin Škoviera. The chromatic number of a signed graph. arXiv: 1412.6349.

[MŠ12]

Bojan Mohar and Simon Špacapan. “Degenerate and star colorings of graphs on surfaces”. In: European J. Combin. 33.3 (2012), pp. 340–349. arXiv: 0806.1242. url: http://dx.doi.org/10.1016/j.ejc.2011.09.007.

[MST]

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

[PA]

Mohammad R. Piri and Saeid Alikhani. Introduction to dominated edge chromatic number of a graph. arXiv: 2003.10232.

[PP16]

Hugo Parlier and Camille Petit. “Chromatic numbers of hyperbolic surfaces”. In: Indiana Univ. Math. J. 65.4 (2016), pp. 1401–1423. arXiv: 1411.3565. url: https://doi.org/10.1512/iumj.2016.65.5842.

[PZ]

A. Poghosyan and V. Zverovich. Discrepancy and Signed Domination in Graphs and Hypergraphs. arXiv: 0906.3993.

[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]

Hossein Shahmohamad. The History of the Total Chromatic Number Conjecture. arXiv: 1104.3170.

[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.

[Tah]

Ali Taherkhani. r-Dynamic Chromatic Number of Graphs. arXiv: 1401.6470.

[Yos]

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

[Zhu21]

Xuding Zhu. “Relatively small counterexamples to Hedetniemi’s conjecture”. In: J. Combin. Theory Ser. B 146 (2021), pp. 141–150. arXiv: 2004.09028. url: https://doi.org/10.1016/j.jctb.2020.09.005.