Acyclic coloring and feedback vertex set of a line digraph

• 河合 博之

Bibliographic Information

Other Title

• ラインダイグラフの無閉路彩色とフィードバック頂点集合

Abstract

無閉路彩色とは，隣接する 2 頂点が異なる色で割当てられ，かつどの 2 色で誘導される部分グラフも閉路を持たない頂点彩色である．一方フィードバック頂点集合は，それを削除することにより閉路を持たないような頂点集合をいう．ここでは，有向グラフのある辺彩色がそのラインダイグラフの底グラフに対する無閉路彩色を与えることを示し，ラインダイグラフに関連するグラフのクラス （de Bruijn グラフや Kautz グラフ等） の無閉路彩色問題およびフィードバック頂点集合問題について考察する．An acyclic coloring of a graph G is a coloring of its vertices, satisfying that no two adjacent vertices are assigned the same color and no two colors induce a cycle in G. A feedback vertex set of a graph G is a subuset S of V (G) such that V (G) ＼ S induces an acyclic subgraph. There are some types of arc-colorings of a digraph in terms of adjacency. In this report, it is shown that a kind of arc-cloring of a digraph gives a acyclic coloring of an underlying graph of a line dgraph. Then, we consider the problem of acyclic coloring and feedback vertex set of graphs related to line digraphs such as de Bruijn graphs or Kautz graphs.

Journal

• 研究報告アルゴリズム（AL）

  研究報告アルゴリズム（AL） 2012 (3), 1-2, 2012-09-27

Details

• CRID: 1573105977731791872
• NII Article ID: 110009455731
• NII Book ID: AN1009593X
• Text Lang: ja
• Data Source:
  • CiNii Articles
  • KAKEN