非環式着色

グラフ理論において、非巡回彩色とは、すべての 2 彩色部分グラフが非巡回となる(適切な)頂点彩色である。グラフGの非巡回彩色数A( G )は、 Gの任意の非巡回彩色に必要な色数の最小値である。

非巡回着色は、非平面上に 埋め込まれたグラフに関連付けられることが多いです。

Gが非巡回である場合に限り、A( G )≤2となる。

Gの最大次数Δ( G )に関するA( G ) の境界には次のものが含まれます。

• Δ( G ) = 3の場合にはA( G )≤4となる。 (Grünbaum 1973)
• Δ( G ) = 4の場合にはA( G ) ≤ 5となる。(Burstein 1979)
• Δ( G ) = 5 の場合、 A( G ) ≤ 7。 (Kostochka & Stocker 2011)
• Δ( G ) = 6 の場合、 A( G ) ≤ 12 (Varagani et al. 2009)

非巡回彩色研究における画期的な出来事は、グリュンバウムの予想に対する次の肯定的な答えです。

定理（Borodin 1979）Gが平面グラフの場合、A( G )≤5 。

Grünbaum (1973) は、非巡回着色と非巡回彩色数を導入し、上記の定理の結果を推測しました。ボロディンの証明には、450 の可約構成の数年間にわたる入念な調査が必要でした。この定理の 1 つの帰結は、すべての平面グラフが 1 つの独立集合と 2 つの誘導 フォレストに分解できることです。(Stein 1970、1971)

A( G )≤3で あるかどうかを判断することはNP完全である。 (Kostochka 1978)

Coleman & Cai (1986)は、 Gが二部グラフであっても、問題の決定変種はNP完全であることを示した。

Gebremedhin ら (2008) は、弦グラフのすべての適切な頂点彩色は非巡回彩色でもあることを実証しました。弦グラフは O( n + m ) 時間で最適に彩色できるため、そのクラスのグラフの非巡回彩色についても同じことが言えます。

最大次数 ≤ 3 のグラフを 4 色以下で非循環的に色付けする線形時間アルゴリズムは、Skulrattanakulchai (2004) によって提案されました。

• 星の塗り絵

• ボロディン、OV（1979）、「平面グラフの非巡回着色について」、離散数学、25（3）：211–236、doi：10.1016/0012-365X（79）90077-3。
• Burstein, MI (1979)、「すべての 4 価グラフには非環式 5 色付けがある (ロシア語)」、Soobšč. Akad. Nauk Gruzin. SSR、93 : 21–24。
• Grünbaum, B. (1973)、「平面グラフの非巡回着色」、イスラエル数学ジャーナル、14 (4): 390–408、doi :10.1007/BF02764716、S2CID  122808877
• Coleman, Thomas F. ; Cai, Jin-Yi (1986)、「巡回着色問題とスパースヘッセ行列の推定」(PDF)、SIAM Journal on Algebraic and Discrete Methods、7 (2): 221–235、doi :10.1137/0607026、hdl : 1813/6485。
• Fertin, Guillaume; Raspaud, André (2008)、「最大次数 5 のグラフの非巡回着色: 9 色で十分」、Information Processing Letters、105 (2): 65–72、CiteSeerX  10.1.1.78.5369、doi :10.1016/j.ipl.2007.08.022、S2CID  12886305。
• Gebremedhin, Assefaw H.; Tarafdar, Arijit; Pothen, Alex; Walther, Andrea (2008)、「カラーリングと自動微分化を使用したスパースヘッセ行列の効率的な計算」、INFORMS Journal on Computing、21 (2): 209–223、doi :10.1287/ijoc.1080.0286。
• ジェンセン、トミー R.; トフト、ビャルネ (1995)、グラフカラーリング問題、ニューヨーク: ワイリー・インターサイエンス、ISBN 978-0-471-02865-9。
• コストカ、AV (1978)、グラフの彩色関数の上限、博士論文（ロシア語）、ノボシビルスク{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)。
• Kostochka, Alexandr V.; Stocker, Christopher (2011)、「最大次数 5 のグラフは非巡回的に 7 色可能である」、Ars Mathematica Contemporanea、4 (1): 153–164、doi : 10.26493/1855-3974.198.541、MR  2785823。
• Skulrattanakulchai, San (2004)、「サブキュービックグラフの非巡回着色」、Information Processing Letters、92 (4): 161–167、doi :10.1016/j.ipl.2004.08.002。
• スタイン、SK（1970）、「B集合と着色問題」、アメリカ数学会誌、76（4）：805–806、doi：10.1090 / S0002-9904-1970-12559-9。
• スタイン、SK（1971）、「B集合と平面マップ」、パシフィックジャーナルオブ数学、37（1）：217–224、doi：10.2140 / pjm.1971.37.217。
• Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009)、「最大次数 6 のグラフの非巡回頂点着色」、LAGOS'09 – 第 5 回ラテンアメリカ アルゴリズム、グラフ、最適化シンポジウム、Electronic Notes in Discrete Mathematics、vol. 35、Elsevier、pp. 177–182、doi :10.1016/j.endm.2009.11.030、MR  2579427

• 星色付けと非環式色付け (1973)、イリノイ大学大学院生研究体験会 (REGS) で発表、2008 年。
• 最大次数 ∆ のグラフの非巡回着色、2005 年ベルリンの EUROCOMB 05 で G. Fertin と A. Raspaud が発表した講演スライド。