文献

J-GLOBAL ID：201702273620824091   整理番号：17A0963079

グラフの不適切な対の端部彩色の複雑性

Complexity of the Improper Twin Edge Coloring of Graphs

著者 (4件)： ABEDIN Paniz (Sharif Univ. Technol., Tehran, IRN) ,  AKBARI Saieed (Sharif Univ. Technol., Tehran, IRN) ,  DEMANGE Marc (RMIT Univ., Victoria, AUS) ,  EKIM Tinaz (Bogazici Univ., Istanbul, TUR)
資料名： Graphs and Combinatorics  (Graphs and Combinatorics)
巻： 33  号： 4  ページ： 595-615  発行年： 2017年 
JST資料番号： X0108A  ISSN： 0911-0119  CODEN： GRCOE5  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： グラフGの不適切な対の端部彩色に取り組んだ。それらは近接しているけれども,彩色数の和と不適切な対の彩色指数は同じではないことに注目すべきである。つまり,グラフGに関して,Gの不適切な対の彩色指数:Χ^’_it(G)は,Gの彩色数の群の和を超さない。彩色数の群の和が不適切な対の彩色指数よりも大きい事例が,ここにある。K₄とK₂の直和を検討し,K₂の1つの頂点にK₄の1つの頂点を近接させて,Gによる連結(resultant)グラフと呼ぶ。次数列:4,3,3,3,2,1を有する位数6のGに注目する。このグラフは不細工(ugly)であって,不細工なグラフはΧ(G)+1の彩色数の群の和を持つから,Gの彩色数の群の和は5である。しかし,Gの不適切な対の彩色指数は4であることを定理に基づいて説明した。

シソーラス用語： *グラフ理論 ,  端部 ,  *数値 ,  彩色問題 ,  *性質 ,  頂点 ,  比較 ,  グラフ
準シソーラス用語： 一対比較 ,  *彩色数 ,  *複雑性 ,  連結グラフ

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

引用文献 (19件)：

• Addario-Berry, L., Aldred, R.E.L., Dalal, K., Reed, B.A.: Vertex colouring edge partitions. J. Comb. Theory (B) 94, 237-244 (2005)
• Andrews, E., Helenius, L., Johnston, D., VerWys, J., Zhang, Ping: On twin edge colorings of graphs. Discuss. Math. Graph Theory 34, 613-627 (2014)
• Anholcer, M., Cichacz, S.: Group sum chromatic number of graphs. Eur. J. Comb. 55, 73-81 (2016)
• Anholcer, M., Cichacz, S., Milanič, M.: Group irregularity strength of connected graphs. J. Comb. Optim. 30(1), 1-17 (2015)
• Appel, K., Haken, W.: The solution of the four-color map problem. Sci. Amer. 237, 108-121 (1977)

タイトルに関連する用語 (3件)： グラフ ,  彩色 ,  複雑性