抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
Tuza[1992]は,1つのモジュロkに一致しない長さのサイクルのないグラフがk-着色可能であることを証明した。グラフGがエッジeを持つならば,G-eがk-彩色性であり,Gが2≦r≦kの場合,エッジeはGにおける長さ1modrの少なくともΠ_i=1 ̄r-1(k-i)サイクルにあり,G-eは長さ0modrの少なくとも1/2Π_i=1 ̄r-1(k-i)サイクルを含むことを証明した。Gの(k,d)-着色は,d≦j-i≦k-dならば,iとjを隣接して定義される頂点集合Z_kを持つGからグラフK_k:dへのホモモルフィズムである。kとdが相対的に主である場合,sd≡1modkによってsを定義する。Zhu[2002]の結果は,Gが,任意のi≡1,2d-1}に対してモジュロkである長さを有するサイクルCを持たないとき,Gが(k,d)着色可能であることを意味する。事実,dクラスのみを除外する必要がある:もしG-eが(k,d)-着色可能であり,Gがそうでないならば,eは,{1,..,d}におけるいくつかのiに対してmod kである長さで少なくとも1つのサイクルにあることを証明した。さらに,これがi∈{1,d-1}で生じないならば,eは長さ1modkで少なくとも2サイクルにあり,G-eは長さ0modkのサイクルを含む。【JST・京大機械翻訳】