文献

J-GLOBAL ID：202202270073726842   整理番号：22A1115464

頂点彩色(4K1,ホールツイン,5輪)フリーグラフ【JST・京大機械翻訳】

Vertex coloring (4K ₁, hole-twin, 5-wheel)-free graphs

著者 (3件)： Dai Yingjun (Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada) ,  Foley Angele M. (Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada) ,  Hoang Chinh T. (Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, Canada)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 914  ページ： 14-22  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最近,グラフの与えられた集合Fに対してFフリーであるグラフGに対するVERTEX COLORING問題に対する多項式時間アルゴリズムの発見に関心が寄せられている。Lが4頂点グラフのセットであるならば,LフリーグラフのためのVERTEX COLORINGの複雑性は,3つの例外によって知られている:L1={claw,4K1},L2={claw,4K1,co-ダイヤモンド},およびL3={4K1,C4}。本論文では,クラスL3から生じる問題を研究した。穴は少なくとも4つの頂点を有する誘導サイクルである。穴-双晶は,穴の幾つかの頂点を持つ真の双晶を形成する頂点を加えることによって,穴から得られたグラフである。5輪は,C5のすべての頂点に隣接している頂点を加えることによって,C5から得られたグラフである。(4K1,穴-双晶,5輪)フリーグラフが完全であるか,または有界クリーク幅を持つことを証明した。結果として,VERTEX COLORINGの多項式時間アルゴリズムを(4K1,正孔-双晶,5輪)フリーグラフに対して得た。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *グラフ ,  正孔 ,  双晶 ,  ダイヤモンド ,  *発色 ,  集合 ,  限界 ,  彩色問題 ,  *頂点
準シソーラス用語： 複雑性 ,  多項式時間アルゴリズム ,  有界 ,  グラフ彩色 , 【Automatic Indexing@JST】

著者キーワード (3件)： グラフ彩色 ,  ホールツイン ,  5輪

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

タイトルに関連する用語 (4件)： 頂点 ,  彩色 ,  ホール ,  グラフ