文献

J-GLOBAL ID：201702286741389114   整理番号：17A1419616

ダイヤモンドない彩色グラフ【Powered by NICT】

Colouring diamond-free graphs

著者 (3件)： Dabrowski Konrad K. (School of Engineering and Computing Sciences, Durham University, Science Laboratories, South Road, Durham DH1 3LE, United Kingdom) ,  Dross Francois (Universite de Montpellier, France - Laboratoire d’Informatique, de Robotique et de Microelectronique de Montpellier, France) ,  Paulusma Danieel (School of Engineering and Computing Sciences, Durham University, Science Laboratories, South Road, Durham DH1 3LE, United Kingdom)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 89  ページ： 410-431  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 彩色問題は決定のグラフGと整数kが与えられた時,Gは(適切な)k-色付けを許容する。最大五頂点H全てのグラフに対し,(ダイヤモンド,H)-フリーグラフの彩色の計算量を分類した。著者等の証明は,クリーク幅は(ダイヤモンド,P一二P2)-フリーグラフのための有界であることを証明と既知の結果を結合することに基づいている。この症例を扱うための本技術は非常に特異的な分解を持つことをk組グラフに考慮したグラフを低減することである。この一般的な手法の副産物として,四つの他の新しいクラス(H 1 , H 2)-フリーグラフのクリーク幅の有界性を証明することもできた。そのようなものとして,著者らの研究は,(H 1 , H 2)-フリーグラフのクリーク幅の(非)有界性に関する最近の系統的な研究を続け,有界クリーク幅の五つの新しいクラスは開放症例の数を減らす13~8。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *グラフ ,  彩色問題 ,  *ダイヤモンド ,  着色 ,  *発色 ,  計算量
準シソーラス用語： 有界 , 【Automatic Indexing@JST】

著者キーワード (4件)： グラフ着色 ,  ダイアモンドのない ,  クリークwidth ,  禁止誘導部分グラフ

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (3件)： ダイヤモンド ,  彩色 ,  グラフ