文献

J-GLOBAL ID：202202263281929407   整理番号：22A0468173

点分割数:パーフェクトグラフ

Point Partition Numbers: Perfect Graphs

著者 (3件)： von Postel Justus (Technische Universitaet Ilmenau, Ilmenau, Germany) ,  Schweser Thomas (Technische Universitaet Ilmenau, Ilmenau, Germany) ,  Stiebitz Michael (Technische Universitaet Ilmenau, Ilmenau, Germany)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 2  ページ： 31  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文で扱うグラフは有限であり無向でループがないが,複数のエッジを持つ。整数t≧1について,その最大多重度がたかだかtであるグラフのクラスをMg_tという。Hにおけるその次数がたかだかt-1である頂点vを含むその空でない全ての部分グラフHが,Hにおける次数がたかだかt-1である頂点vを含む場合に,グラフGは厳密にt縮退していると呼ぶ。Gの点分割数χ_t(G)は,各頂点に色を付け,同じ色を付けた頂点がGの厳密にt-縮退した部分グラフを誘導するように,Gの頂点を彩色するために必要な色の最小数である。そのためχ₁は彩色数でありχ₂は点樹相度として知られる。t≧1について点分割数χ_tが,LickとWhiteによって紹介された(Can J Math22:1082-1096,1970)。Hが単純グラフならば,tHはHの各辺をt個の平行辺で置換えることによりHから得られたグラフを表す。このとき,ω_t(G)は,GがtK_nを部分グラフとして含むような最大の整数nである。GをMg_tに属するグラフとする。そのとき,ω_t(G)≦χ_t(G)を満たし,Gの全ての誘導部分グラフHがω_t(H)=χ_t(H)を満たすならばGはχ_t-パーフェクトであると言う。Chudnowsky,Robertson,SeymourとThomasによる強パーフェクトグラフ理論(Ann Math164:51-229,2006)に基づき,禁止誘導部分グラフの集合によりMg_tのχ_t-パーフェクトグラフを特徴付ける(定理2,3参照)。また,χ_t-パーフェクトグラフのクラスについていくつかの複雑性問題も議論する.Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2021 Translated from English into Japanese by JST.

シソーラス用語： ループ ,  無向グラフ ,  端部 ,  *部分グラフ ,  無次元数 ,  頂点 ,  *彩色問題 ,  数値 ,  *縮退 ,  *分割 ,  誘導 ,  分類
準シソーラス用語： エッジ ,  ガジェット ,  クラス ,  彩色数 ,  次数

著者キーワード (3件)： 点分割数 ,  縮退 ,  完全グラフ

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

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