文献

J-GLOBAL ID：201602218788299918   整理番号：16A0004139

キャタピラーの調和のとれたカラーリングに関する一考察

A Note on Harmonious Coloring of Caterpillars

著者 (4件)： TAKAOKA Asahi (Dep. of Communications and Computer Engineering, Tokyo Inst. of Technol.) ,  OKUMA Shingo (Dep. of Communications and Computer Engineering, Tokyo Inst. of Technol.) ,  TAYU Satoshi (Dep. of Communications and Computer Engineering, Tokyo Inst. of Technol.) ,  UENO Shuichi (Dep. of Communications and Computer Engineering, Tokyo Inst. of Technol.)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E98.D  号： 12  ページ： 2199-2206 (J-STAGE)  発行年： 2015年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 無向単純グラフの調和のとれたカラーリングは,隣接頂点を異なった色に割り当てて,各組の色がほぼ1つのエッジで一緒に出現するような頂点カラーリングである。グラフの調和のとれた彩色数は,そのようなカラーリングに使用した最少の数の色であった。経路の調和のとれた彩色数は既知であるが,調和のとれた彩色数を見つける問題は,ほぼ2のパス幅をもつツリーとして考えてもNP困難であった。したがって,著者らは,パス幅1を用いるツリーの調和のとれたカラーリングを検討したが,それは,キャタピラーとして既知であった。本稿は,1つの頂点を使用するキャタピラーの調和のとれた2以上程度の彩色数を示した。また,著者らは,3つの通常のキャタピラーの調和のとれた彩色数の上限を示した。(翻訳著者抄録)

シソーラス用語： *履帯 ,  *色 ,  グラフ理論 ,  無向グラフ ,  頂点 ,  数値 ,  NP困難 ,  経路
準シソーラス用語： *キャタピラ ,  *カラー ,  単純グラフ ,  彩色数

分類 (2件)： 色  (BD03090A) ,  その他の情報処理  (JE15050M)

引用文献 (18件)：

• [1] A. Aflaki, S. Akbari, K.J. Edwards, D.S. Eskandani, M. Jamaali, and H. Ravanbod, “On harmonious colouring of trees,” Electr. J. Comb., vol.19, no.1, pp.1-9, 2012.
• [2] S. Akbari, J. Kim, and A. Kostochka, “Harmonious coloring of trees with large maximum degree,” Discrete Math., vol.312, no.10, pp.1633-1637, 2012.
• [3] K. Asdre, K. Ioannidou, and S.D. Nikolopoulos, “The harmonious coloring problem is NP-complete for interval and permutation graphs,” Discrete Appl. Math., vol.155, no.17, pp.2377-2382, 2007.
• [4] K. Asdre and S.D. Nikolopoulos, “NP-completeness results for some problems on subclasses of bipartite and chordal graphs,” Theor. Comput. Sci., vol.381, no.1-3, pp.248-259, 2007.
• [5] H.L. Bodlaender, “Achromatic number is NP-complete for cographs and interval graphs,” Inform. Process. Lett., vol.31, no.3, pp.135-138, 1989.

タイトルに関連する用語 (3件)： キャタピラー ,  調和 ,  カラー