ラインダイグラフの無閉路彩色とフィードバック頂点集合  [in Japanese] Acyclic coloring and feedback vertex set of a line digraph  [in Japanese]

Access this Article

Search this Article

Author(s)

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-AL-141(3), 1-2, 2012-09-27

Codes

  • NII Article ID (NAID)
    110009455731
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    JPN
  • Article Type
    Technical Report
  • Data Source
    NII-ELS  IPSJ 
Page Top