文献

J-GLOBAL ID：201702274178867829   整理番号：17A1754451

4-正則グラフ彩色のKempe等価性【JST・京大機械翻訳】

Kempe Equivalence of Colorings of 4-regular Graphs

著者 (2件)： Liu Xiaoqing (北京大学信息科学技術学院 北京 100871) ,  Xu Jin (北京大学信息科学技術学院 北京 100871;北京大学高可信軟件技術教育部重点実験室 北京 100871)
資料名： Dianzi yu Xinxi Xuebao  (Dianzi yu Xinxi Xuebao)
巻： 39  号： 5  ページ： 1233-1244  発行年： 2017年 
JST資料番号： C2507A  ISSN： 1009-5896  CODEN： DKXUEC  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 中国 (CHN)  言語： 中国語 (ZH)

抄録/ポイント： グラフGとその1つの正常頂点着色f,G中の任意の2種類の色の頂点導出部分グラフをGの一つの2-色導出部分グラフと呼び,この2-色導出部分グラフの分枝をGの1-2色分枝と呼び,KG変換は図Gのある2-色分枝を色交換する。........................................................を与える.2の色を導出する.2の色の部分グラフである.2の色を導出する.もし2つの着色の間にいくつかのKempe変換を通して相手に達するならば,これらの2つの着色はKempeの等価であり,Moharはk≧3のとき,任意の連結k-正則グラフGに対して完全なグラフではない。Gのすべてのk-着色はKempeが等価であることを示し、Feghaliらはk=3時の状況を解決し、k≧4の場合、この予想はまだ解決されていない。本論文では,k=4の場合について検討した。(1)もしGが連結度が3より小さい4-正則グラフであれば、Gのすべての4-着色はKempe等価である。(2)Gが4-正則グラフであり、しかも4-ラウンドまたは近5-階完全グラフと同形の部分グラフを含むならば、Gのすべての4-着色はKempe等価である。(3)もしGが3-連結4-正則グラフであり、Gが頂点xと1-4色fが存在し、xの近傍に3つまたは4つの頂点がfで同じ色を持つならば、Gのすべての4-着色はKempe等価である。Data from Wanfang. Translated by JST【JST・京大機械翻訳】

シソーラス用語： 等価性 ,  *グラフ ,  完全グラフ ,  部分グラフ ,  着色
準シソーラス用語： *正則グラフ ,  色変換 ,  グラフ彩色 , 【Automatic Indexing@JST】

著者キーワード (4件)： Kempe equivalent ,  Kempe change ,  Kempe equivalent class ,  4-regular graph

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 正則グラフ ,  彩色 ,  等価性