グラフ理論入門 ２ 彩色

２　グラフの彩色(coloring)

• グラフの彩色には、頂点彩色と辺彩色とがある。

2.1　頂点彩色

• 頂点彩色
  
  • グラフにあって、隣接するどの2頂点も同色にならないように、全頂点に色を対応させることを、頂点の彩色という。
• (頂点)彩色数(chromatic number,χ(G))
  
  • グラフGに対して、Gの(頂点)彩色に必要な色の最小数を(頂点)彩色数と言う。
• (頂点)彩色数についての基本事項
  
  • p頂点のグラフの彩色数はp以下である。
  • また、彩色数がpであるような、p頂点のグラフはKpに限られる。
• 臨界(critical)
  
  • Gの任意の真部分グラフHについて、χ(H)＜χ(G)が成り立つとき、Gは臨界であると言う。
• 内周(girth)
  
  • グラフ内の最短サイクルの長さのこと。
• 2部グラフの彩色数による定義
  
  • χ(G)<=２のとき、Gが2部グラフ(bipartite)である。

2.2　辺彩色

• 辺彩色
  
  • グラフGの辺に色を指定することであり、頂点彩色のそれとことなり、制限はない。
• 固有辺彩色(proper edge coloring)
  
  • どの隣接する2辺も異なる色で塗るという条件における、辺彩色のこと。
• 辺彩色数(edge chromatic number)
  
  • Gの固有辺彩色に必要な最小の色の数。

2.3　分解とハミルトンサイクル

• 分解(decomposition,decomposed,decomposable)
  
  • グラフGのすべての辺集合の要素を、複数の部分集合に分け、すべての辺が１つの部分集合にしか属さず、また、すべての辺が必ずいずれかの部分集合に属するようにしたときに、辺の部分集合とその端頂点からなるGの部分集合に分解された、と言う。
• ハミルトンサイクル(Hamilton cycle)
  
  • グラフGの最長サイクルであって、すべての頂点を含むものをハミルトンサイクルと呼ぶ。
• 思いつきメモ
  
  • TagSNP問題は彩色問題に還元できるのではないか