文献

J-GLOBAL ID：201802227494912248   整理番号：18A1191040

サブキュービック多重グラフの星色指数【JST・京大機械翻訳】

Star chromatic index of subcubic multigraphs

著者 (3件)： Lei Hui (Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China) ,  Shi Yongtang (Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China) ,  Song Zi-Xia (Department of Mathematics, University of Central Florida, Orlando, FL 32816, USA)
資料名： Journal of Graph Theory  (Journal of Graph Theory)
巻： 88  号： 4  ページ： 566-576  発行年： 2018年 
JST資料番号： C0773B  ISSN： 0364-9024  CODEN： JGTHD  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 多重グラフGの星の色指数(χs′(G))は,長さ4の経路や周期が双極化されないようなGのエッジを適切に色するために必要な最小数の色である。多重グラフGは,χs′(G)≦kならば,星kエッジ色である。Dvorak,Mohar,およびSamal[Star色指数,J.Graph理論72(2013),313-326]は,すべてのサブキューブマルチグラフが星7-エッジ-着色可能であることを証明した。それらは,すべてのサブキューブマルチグラフが星の6-エッジ-着色可能であるべきであるという同じ論文において推測した。本論文では,まず,任意のグラフGに対してχs′(G)≦3を決定することがNP完全であることを証明した。これはMoharの疑問に答える。次に,k∈{5,6}の任意のv∈V(G)に対してχs′(G)>k,χs′(G-V)≦kのようなδ(G)≦2をもつ部分立方多重グラフGに関するいくつかの構造結果を確立した。最後に,単純な放電法と共に構造結果を適用し,mad(G)<5/2の場合にはすべてのサブキューブマルチグラフGが星型6エッジ色であり,mad(G)<24/11の場合には星の5エッジ色が多グラフGの最大平均次数であることを証明した。これは,Dvorak,Mohar,Samalの予測を部分的に確認した。Copyright 2018 Wiley Publishing Japan K.K. All Rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *色指数 ,  放電 ,  *多重化 ,  着色 ,  *グラフ
準シソーラス用語： 次数 , 【Automatic Indexing@JST】

著者キーワード (3件)： 最大平均次数 ,  星エッジ彩色 ,  サブキュービック多重グラフ

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

タイトルに関連する用語 (4件)： 多重 ,  グラフ ,  星 ,  色指数