文献

J-GLOBAL ID：201802210189429508   整理番号：18A0709615

局所的に連結した部分グラフの三角形への収縮により特性化された3つの着色可能性【JST・京大機械翻訳】

Three colorability characterized by shrinking of locally connected subgraphs into triangles

著者 (1件)： Kochol Martin (MU SAV, Stefanikova 49, 814 73 Bratislava 1, Slovakia)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 135  ページ： 33-35  発行年： 2018年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： ここでは,各3色の局所的に接続された部分グラフが三角形により置き換えられるようなグラフの再帰的な縮小を考察し,等しく着色された頂点が一つの頂点に一致するようにした。元のグラフの3色と縮小から生じるグラフの間には1対1の対応がある。このアプローチを用いて,3色グラフのクラスを特性化し,クラスからグラフを認識する多項式時間アルゴリズムを提示し,それらを3つの色によりカラー化した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *着色 ,  *部分グラフ ,  *グラフ ,  *キャラクタリゼーション
準シソーラス用語： 多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： 局所連結グラフ ,  3色性 ,  δ-還元 ,  (強)δ可約グラフ ,  グラフアルゴリズム

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (6件)： グラフ ,  三角形 ,  収縮 ,  特性化 ,  着色 ,  可能性