ミシェルスキアン

数学のグラフ理論の分野において、無向グラフのミシェルスキアングラフまたはミシェルスキグラフは、ヤン・ミシェルスキ(1955)の構成によって形成された、より大きなグラフです。この構成は三角形 がないという特性を保持しますが、彩色数が増加します。三角形がない開始グラフにこの構成を繰り返し適用することで、ミシェルスキは、彩色数が任意に大きい三角形がないグラフが存在することを示しました。

与えられたグラフGのn 個の頂点をv ₁、v ₂、...、v _nとします。Mycielski グラフ μ( G ) には、 G自体がサブグラフとして含まれ、さらにn +1 個の追加の頂点、つまりGの各頂点v _iに対応する頂点u _iと、追加の頂点wが含まれます。各頂点u _iは辺によってwに接続されているため、これらの頂点は星型K _{1, n}の形でサブグラフを形成します。さらに、Gの各辺v _i v _jに対して、Mycielski グラフにはu _i v _jとv _i u _{j の}2 つの辺が含まれます。

したがって、Gにn個の頂点とm個の辺がある場合、μ( G )には2n +1個の頂点と3m + n個の辺があります。

μ( G )内の唯一の新しい三角形は、v _i v _j u _kの形式です。ここで、 v _i v _j v _kはG内の三角形です。したがって、Gに三角形がない場合は、 μ( G ) も三角形がなくなります。

構築によって彩色数が増加することを確認するには、の適切なk色付け、つまり、隣接する頂点x、yに対するのマッピングについて考えます。すべてのiに対してが成立する場合、 のとき はによってGの適切な ( k −1) 色付けを定義できます。それ以外の場合は です。しかし、 ではこれは不可能であるため、c はに対してすべてのk色を使用する必要があり、最後の頂点wの適切な色付けでは追加の色を使用する必要があります。つまり、 です。 ${\displaystyle \chi (G)=k}$${\displaystyle \mu (G){-}\{w\}}$${\displaystyle c:\{v_{1},\ldots ,v_{n},u_{1},\ldots ,u_{n}\}\to \{1,2,\ldots ,k\}}$${\displaystyle c(x)\neq c(y)}$${\displaystyle c(u_{i})\in \{1,2,\ldots ,k{-}1\}}$${\displaystyle c'\!(v_{i})=c(u_{i})}$${\displaystyle c(v_{i})=k}$${\displaystyle c'\!(v_{i})=c(v_{i})}$${\displaystyle \chi (G)=k}$${\displaystyle \{u_{1},\ldots ,u_{n}\}}$${\displaystyle \chi (\mu (G))=k{+}1}$

1 辺のグラフから始めて、Mycielskian を繰り返し適用すると、Mycielski グラフと呼ばれることもあるグラフのシーケンスM _i = μ( M _{i −1} ) が生成されます。このシーケンスの最初のいくつかのグラフは、2 つの頂点が 1 つの辺で接続されたグラフM ₂ = K _{2 、}サイクル グラフ M ₃ = C ₅、および11 個の頂点と 20 個の辺を持つ Grötzsch グラフ M _4です。

一般に、グラフM _{i は}三角形がなく、( i −1)頂点連結で、i彩色です。i ≥ 2 の場合のM _iの頂点数は3 × 2 ^{i −2}  − 1 ( OEISのシーケンスA083329 ) ですが、 i = 2, 3, . . . の場合の辺の数は次のとおりです。

1、5、20、71、236、755、2360、7271、22196、67355、...（OEISの配列A122695）。

• G の彩色数 がkであれば、 μ( G ) の彩色数はk  + 1 である (Mycielski 1955)。
• G が三角形を持たない場合、μ( G ) も三角形を持たない (Mycielski 1955)。
• より一般的には、G がクリーク数ω( G )を持つ場合、μ( G ) は 2 と ω( G )のうち最大のクリーク数を持ちます。(Mycielski 1955)
• G が因数臨界グラフである場合、μ( G ) も因数臨界グラフである (Došlić 2005)。特に、i ≥ 2のすべてのグラフM _{i は} 因数臨界である。
• Gにハミルトン閉路がある場合、μ( G )にもハミルトン閉路があります(Fisher、McKenna、Boyer 1998)。
• Gの支配数γ( G )を持つ場合、μ( G )の支配数γ( G )+1を持つ(Fisher、McKenna、Boyer 1998)。

Mycielskian の一般化はグラフ上の円錐と呼ばれ、Stiebitz (1985) によって導入され、Tardif (2001) および Lin ら (2006) によってさらに研究されました。この構築では、テンソル積G × H (ここで H は長さ i で片方の端に自己ループがあるパス) を取り、次にパスのループ で ない端でHの頂点に関連付けられているすべての頂点を単一のスーパー頂点に縮小することによって、与えられたグラフ G からグラフを形成します。Mycielskian 自体は、 μ( G ) = Δ ₂ ( G )としてこのように形成できます。 ${\displaystyle \Delta _{i}(G)}$

円錐構成は必ずしも彩色数を増加させるわけではないが、Stiebitz (1985) は、K ₂に反復的に適用すると彩色数が増加することを証明した。つまり、一般化ミシェルスキアンと呼ばれるグラフ族のシーケンスを次のように定義する。

ℳ(2) = { K ₂ } かつ ℳ( k +1) = { | G ∈ ℳ( k ), i ∈ } である。${\displaystyle \Delta _{i}(G)}$${\displaystyle \mathbb {N} }$

例えば、ℳ(3) は奇サイクルの族である。すると、ℳ( k )の各グラフはk彩色である。証明では、László Lovászによって開発された位相的組合せ論の方法を使用して、クネザーグラフの彩色数を計算する。すると、三角形のない性質は次のように強化される。i ≥ r に対して円錐構築 Δ i のみを適用すると、結果の_グラフの奇内周は少なくとも 2 r + 1になる。つまり、長さが 2 r + 1 未満である奇サイクルは含まれない。このように、一般化された Mycielskian は、彩色数が高く、奇内周が高いグラフの簡単な構築を提供する。

• Chvátal, Vašek (1974)、「Mycielski グラフの最小性」、Graphs and Combinatorics (Proc. Capital Conf.、George Washington Univ.、ワシントン DC、1973)、Lecture Notes in Mathematics、vol. 406、Springer-Verlag、pp. 243–246。
• Došlić, Tomislav (2005)、「Mycielskians とマッチング」、Discussiones Mathematicae Graph Theory、25 (3): 261–266、doi : 10.7151/dmgt.1279、MR  2232992。
• フィッシャー、デビッド C.; マッケナ、パトリシア A.; ボイヤー、エリザベス D. (1998)、「ミシェルスキーのグラフのハミルトン性、直径、支配、パッキング、およびバイクリーク分割」、離散応用数学、84 (1–3): 93–105、doi : 10.1016/S0166-218X(97)00126-1。
• リン・ウェンソン。ウー、ジャンジュアン。ラム、ピーター・チェ・ボール。 Gu, Guohua (2006)、「一般化ミシエルスキアンのいくつかのパラメーター」、離散応用数学、154 (8): 1173–1182、doi : 10.1016/j.dam.2005.11.001。
• Mycielski、Jan (1955)、「Sur le coloriage desgraphes」(PDF)、Colloq。数学。、3 (2): 161–162、ドイ: 10.4064/cm-3-2-161-162。
• Stiebitz, M. (1985)、Beiträge zur Theorie der färbungskritschen Graphen、ハビリテーション論文、Technische Universität IlmenauTardif (2001) より引用。
• Tardif, C. (2001)、「グラフ上の円錐の分数彩色数」、Journal of Graph Theory、38 (2): 87–94、doi :10.1002/jgt.1025。

• Weisstein、Eric W.「Mycielski グラフ」。MathWorld。