文献

J-GLOBAL ID：201702241933364557   整理番号：17A0963087

レインボー道の最適な彩色

Optimal Colorings with Rainbow Paths

著者 (2件)： BENDELE O. (Ulm Univ., Ulm, DEU) ,  RAUTENBACH D. (Ulm Univ., Ulm, DEU)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 729-734  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 頂点集合V(G)を持った有限で簡素な無向グラフをGとする。正整数kに関して,最大をkとする全ての正整数集合を[k]とする。Gのk彩色は関数f,即ち,Gの全ての2つの隣接した頂点uとvに関して,f(u)≠f(v)のようにV(G)→[k]である。Gの彩色数Χ(G)はGがk彩色になるような最小のkであった。n≧2d且つgcd(n,d)=1の正整数nとdに関して,Gの(n,d)彩色は関数c,即ち,Gの全ての2つの隣接した頂点uとvに関して,d≦|c(u)-c(v)|≦n-d,のような,V(G)→[n]である。Gの循環彩色数Χ_c(G)は,Gの全(n,d)彩色のn/dの下限である。参考文献9,10で知られているように,この下限は最小であって,Χ(G)-1<Χ_c(G)<Χ(G)であり,このことは[Χ_c(G)]=Χ(G)であることを暗示している。最終的に,有向の全レインボー道の最適彩色の存在を示した。

シソーラス用語： *道【グラフ】 ,  *発色 ,  数値 ,  無向グラフ ,  循環 ,  下限 ,  グラフ理論 ,  頂点 ,  *最適化
準シソーラス用語： *彩色 ,  彩色数

分類 (1件)： 集合論  (AB10000I)

引用文献 (10件)：

• Akbari, S., Khaghanpoor, F., Moazzeni, S.: Colorful paths in vertex coloring of graphs, preprint
• Akbari, S., Liaghat, V., Nikzad, A.: Colorful paths in vertex coloring of graphs. Electron. J. Combin. 18, (2011) (#P17)
• Alishahi, M., Taherkhani, A., Thomassen, C.: Rainbow paths with prescribed ends, Electron. J. Combin. 18, (2011) (# P86)
• Bessy, S. Bousquet, N.: Colorful paths for 3-chromatic graphs, arXiv:1503.00965v1
• Dean, N., Lesniak, L., Saito, A.: Cycles of length 0 modulo 4 in graphs. Discrete Math. 121, 37-49 (1993)

タイトルに関連する用語 (2件)： レインボー ,  彩色