文献

J-GLOBAL ID：202202215929015746   整理番号：22A0138839

境界付きパレットによる比例2-選択可能性

Proportional 2-Choosability with a Bounded Palette

著者 (4件)： Mudrock Jeffrey A. (Department of Mathematics, College of Lake County, Grayslake, IL, USA) ,  Piechota Robert (Department of Mathematics, College of Lake County, Grayslake, IL, USA) ,  Shin Paul (Department of Mathematics, College of Lake County, Grayslake, IL, USA) ,  Wagstrom Tim (Department of Mathematics, College of Lake County, Grayslake, IL, USA)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 1  ページ： 23  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 要旨:比例選択可能性は,公平な着色の類似物を着色するリストである。具体的には,グラフGのk割り当てLは,k個の使用可能な色のリストL(v)を各v∈V(G)に関連付ける。L着色は,リストL(v)から各頂点vに色を割り当てる。Gの比例着色は,各色c∈U_v∈V(G)L(v)が|η(c)/k|または|η(c)/k|回使用される固有L色で,η(c)=|{v∈V(G):c∈L(v)}|のことである。グラフGは,LがGのk割り当てである場合は常に,Gの比例L着色が存在する場合,比例k選択可能である。以前の研究に動機付けられて,境界パレットを使用した比例2選択可能性を研究することにより,境界パレットを使用した比例選択可能性の研究を開始した。特に,l≧2の場合,Lが|U_v∈V(G)L(v)|≦lを満たすGの2代入であるとき,Gの比例L彩が存在すれば,比例(2,l)-選択可能であるという。グラフが比例的に(2,2)選択可能であるのは,それが等しく2色である場合に限ることを観察した。lが大きくなるにつれて,比例的に(2,l)ふぇ選択可能なグラフの集合は小さくなる。グラフが比例(2,l)-選択可能であるのは,比例2選択可能である場合のみであることを示した。Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2021 Translated from English into Japanese by JST.

シソーラス用語： *図表 ,  *適応性 ,  選択 ,  着色 ,  彩色問題 ,  集合
準シソーラス用語： *カラーパレット ,  グラフ彩色 ,  頂点被覆 ,  *適応可能性

著者キーワード (3件)： グラフ彩色 ,  公平な着色 ,  リスト着色

分類 (2件)： グラフ理論基礎  (IA02020S) ,  応用数学  (AB11000P)

タイトルに関連する用語 (4件)： 境界 ,  パレット ,  比例 ,  選択可能