グラフ理論において、頂点を（互いに素な）等しい大きさのサブセットに分割することに関する強彩とは、あらゆる部分が各色でちょうど1回現れるような（適切な）頂点彩色である。頂点をサイズkの集合に分割するたびに強彩が許されるグラフは、k強彩可能である。グラフGの位数がkで割り切れない場合、新しいグラフG ′の位数がkで割り切れるだけの孤立した頂点をGに追加する。その場合、 G ′の強彩から先に追加された孤立した頂点を除いたものが、 Gの強彩であるとみなされる。[1]
グラフGの強彩色数sχ( G ) は、 Gが強k彩色可能である最小のkである。グラフが強k彩色であるとは、強彩色数kを持つことを意味する。
sχ( G )のいくつかの性質:
- sχ( G ) > Δ( G ) です。
- sχ( G ) ≤ 3 Δ( G ) − 1。[2]
- 漸近的には、sχ( G )≤11Δ( G )/4+o(Δ( G ))である。[3]
ここでΔ( G )は最大次数である。
強彩数はアロン（1988）[4] [5]とフェローズ（1990）[6]によって独立に導入された。
関連する問題
グラフと頂点の分割が与えられたとき、独立横断とは、隣接しない頂点の集合Uであり、各部分にはUの頂点が1つだけ含まれるようなものである。強彩色は、頂点を互いに素な独立横断に分割することと等価である（各独立横断は単一の「色」である）。これは、グラフの頂点を指定された数の独立集合に分割するグラフ彩色とは対照的である。ただし、これらの独立集合が横断である必要はない。
これらの概念の違いを説明するために、複数の学科を持つ学部を考えてみましょう。学部長は教員委員会を設置したいと考えています。しかし、一部の教員は対立関係にあり、同じ委員会に参加しません。この「対立」関係をグラフの辺で表すと、次のようになります。
- 独立したセットは、競合のない委員会です。
- 独立横断委員会は、各部門から 1 人のメンバーだけで構成される、対立のない委員会です。
- グラフの色分けは、教員を対立のない委員会に分割することです。
- 強いカラーリングとは、教員を各学部から1人ずつ、対立のない委員会に分割することです。そのため、この問題は「ハッピー・ディーン問題」と呼ばれることもあります。[7]
参考文献
- ^ Jensen, Tommy R. (1995).グラフ彩色問題. Toft, Bjarne. ニューヨーク: Wiley. ISBN 0-471-02865-7. OCLC 30353850。
- ^ Haxell, PE (2004-11-01). 「強彩色数について」 .組合せ論、確率論、計算. 13 (6): 857– 865. doi :10.1017/S0963548304006157. ISSN 0963-5483. S2CID 6387358.
- ^ Haxell, PE (2008). 「強彩色数の改良された境界」 . Journal of Graph Theory . 58 (2): 148– 158. doi :10.1002/jgt.20300. ISSN 1097-0118. S2CID 20457776.
- ^ Alon, N. (1988-10-01). 「グラフの線形樹状性」.イスラエル数学ジャーナル. 62 (3): 311– 325. doi : 10.1007/BF02783300 . ISSN 0021-2172.
- ^ Alon, Noga (1992). 「グラフの強彩色数」.ランダム構造とアルゴリズム. 3 (1): 1– 7. doi :10.1002/rsa.3240030102.
- ^ Fellows, Michael R. (1990-05-01). 「グラフにおける頂点分割の横断」 . SIAM Journal on Discrete Mathematics . 3 (2): 206– 215. doi :10.1137/0403018. ISSN 0895-4801.
- ^ Haxell, P. (2011-11-01). 「委員会の設置について」 .アメリカ数学月刊. 118 (9): 777– 788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
