著者

猿渡 康文

出版者

情報処理学会

雑誌

情報処理学会研究報告. MPS, 数理モデル化と問題解決研究報告 (ISSN:09196072)

巻号頁・発行日

vol.97, no.113, pp.25-30, 1997-11

---

本稿では, 辺彩色グラフ (edge-colored graphs) と呼ぶ, あらかじめ各辺に彩色がなされたグラフの特徴付について議論する. "一般のグラフ"の特徴付けにおいては, ハミルトン閉路といったグラフのもつ構造を鍵として利用している. "辺彩色グラフ"においては, "一般のグラフ"におけるグラフのもつ構造と共に, 交互性 (alternaty) と呼ぶ構造を導入した特徴付けがなされている. 本稿では, 辺彩色グラフにおける交互性を導入したグラフの特徴付けに関する既往の研究を紹介し, さらに, ある特定の点を端点としてもつハミルトン路をもつ辺彩色グラフの特徴付けを示す.An edge-colored graph is a graph, each of whose edge is colored by some color in advance. This paper treats a characterization of edge-colored graphs. To do so, a structure, so-called alternaty, is introduced. This structure is concerning to colors on edges, and plays an important role in characterizations as well as a graphical structure (e.g. Hamiltonian cycle, etc.). We first summarize some previous works concerning to characterizations of edge-colored graphs, and show a characterization of edge-colored graphs based on a new graphical structure.