文献

J-GLOBAL ID：201802247050514817   整理番号：18A0128403

誘導部分グラフに関するいくつかの問題【Powered by NICT】

Some problems on induced subgraphs

著者 (1件)： Sivaraman Vaidy (Department of Mathematical Sciences, Binghamton University, United States)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 236  ページ： 422-427  発行年： 2018年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 誘導部分グラフに関連したいくつかの問題を議論した。(1)すべての誘導されたサイクルは長さ3または4を持つグラフのためのクリーク数に関して彩色数のための良好な上限。(2)グラフ,グラフの頂点集合を分割できる完全集合の最小数の完全な彩色数。彩色数とクリーク数の差は高々1つである(完全グラフを誘導するかどうかを頂点の集合は完璧であると言われている。)(3)グラフグラフのすべての誘導部分グラフ。(4)悪名高いErdoes Hajnal予想の弱体化。(5)グラフの特定のクラスのχ-有界約Gyarfasの予想。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *部分グラフ ,  *グラフ ,  完全グラフ
準シソーラス用語： 有界 ,  彩色数 , 【Automatic Indexing@JST】

著者キーワード (6件)： 誘導部分グラフ ,  彩色数 ,  クリーク数 ,  禁止誘導部分グラフ ,  NP完全性 ,  完全グラフ

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

タイトルに関連する用語 (2件)： 誘導 ,  部分グラフ