| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2008-01-31 13:50 n/k-彩色に関する階層構造間に存在する平面グラフの構成手法 ○井口雄弥・庄司將一・上嶋章宏（阪電通大）  CAS2007-86 |
|
| 抄録 | （和） | 古典的なn-彩色では，色数n の増加に伴い彩色可能なグラフは真に増加し，n-彩色に関する自明な階層構造が存在する．n-彩色の一般化であるn/k-彩色はその階層構造を真に細分する性質を持ち，n'/k' < n/k に対しn'/k'-彩色可能なグラフは全てn/k-彩色可能であるが，その逆は成立しない．一方，2 < n/k < 3 に対し，平面グラフのn/k-彩色問題がNP 完全性であることが示されており，計算量の観点では当該範囲のn/k に対し違いがない．そこで本研究では，2 < n'/k' < n/k < 3 に関する階層構造に注目し，階層構造間に存在する平面グラフの構成を示すことで，2 < n'/k' < n/k < 3 に対し，平面グラフに対象を限定してもn'/k'-彩色とn/k-彩色に明確な能力差があることを示す． |
| （英） | The typical vertex n-colorings have trivial inclusion relations of classes of n-colorable graphs for the escalating number of colors. The inclusions can be subdivided by the n/k-colorings, which is a natural generalization of vertex colorings. Namely, n'/k'-colorable graphs are n/k-colorable, however, the converse propositions are incorrect for any fraction numbers n'/k', n/k such that n'/k' < n/k. On the other hand, it has already shown that n/k-coloring problems of planar graphs are NP-complete for any n/k with 2 < n/k < 3, thus there are no difference for such n/k from the viewpoint of the computational complexity. This paper takes notice the inclusion relations of classes of n/k-colorable planar graphs, and presents that there exists articulate difference between the classes of n'/k'-, n/k-colorable planar graphs for any n'/k', n/k such that 2 < n'/k' < n/k < 3, by showing the construction method of the planar graphs in the difference sets. | |
| キーワード | （和） | n-彩色 / n/k-彩色 / 階層構造 / 平面グラフ / Circular Coloring / / / |
| （英） | n-coloring / n/k-coloring / Hierarchy Structure / Planar Graph / Circular Coloring / / / | |
| 文献情報 | 信学技報, vol. 107, no. 475, CAS2007-86, pp. 13-18, 2008年1月. | |
| 資料番号 | CAS2007-86 | |
| 発行日 | 2008-01-24 (CAS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2007-86 |
|
| 研究会情報 | |
| 研究会 | CAS |
| 開催期間 | 2008-01-31 - 2008-02-01 |
| 開催地（和） | 沖縄県青年会館 |
| 開催地（英） | |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | CAS |
| 会議コード | 2008-01-CAS |
| 本文の言語 | 日本語 |
| タイトル（和） | n/k-彩色に関する階層構造間に存在する平面グラフの構成手法 |
| サブタイトル（和） | |
| タイトル（英） | The constitution method of planar graphs existing between hierarchy structure for n/k-colorings |
| サブタイトル（英） | |
| キーワード(1)（和/英） | n-彩色 / n-coloring |
| キーワード(2)（和/英） | n/k-彩色 / n/k-coloring |
| キーワード(3)（和/英） | 階層構造 / Hierarchy Structure |
| キーワード(4)（和/英） | 平面グラフ / Planar Graph |
| キーワード(5)（和/英） | Circular Coloring / Circular Coloring |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 井口 雄弥 / Yuya Iguchi / イグチ ユウヤ |
| 第1著者 所属（和/英） | 大阪電気通信大学 (略称： 阪電通大) Osaka Electro-Communication University (略称： Osaka Electro-Communication Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 庄司 將一 / Masakazu Shoji / ショウジ マサカズ |
| 第2著者 所属（和/英） | 大阪電気通信大学 (略称： 阪電通大) Osaka Electro-Communication University (略称： Osaka Electro-Communication Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 上嶋 章宏 / Akihiro Uejima / ウエジマ アキヒロ |
| 第3著者 所属（和/英） | 大阪電気通信大学 (略称： 阪電通大) Osaka Electro-Communication University (略称： Osaka Electro-Communication Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2008-01-31 13:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CAS |
| 資料番号 | CAS2007-86 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.475 |
| ページ範囲 | pp.13-18 |
| ページ数 | 6 |
| 発行日 | 2008-01-24 (CAS) |
[研究会発表申込システムのトップページに戻る]