調和のとれた色彩

リンクされた2つのノードが同じ色の組み合わせを持たない頂点カラーリング

グラフ理論において、調和彩色とは、すべての色の組み合わせが隣接する頂点の組のうち最大で1組にしか現れないような（適切な）頂点彩色である。これは、すべての色の組み合わせが少なくとも1回は現れる完全彩色とは逆である。グラフ $G$ の調和彩色数 $χ$ $H$ $($ $G$ $)は、$ $G$ の任意の調和彩色に必要な最小の色数である。

すべてのグラフは調和的な彩色を持つ。これは、すべての頂点に異なる色を割り当てるだけで十分であるためである。したがって、 $χ H (G) \leq | V(G) |$ となる。 $χ$ $H$ $($ $G$ $) > χ($ $G$ $)$ （ここで $χ$ は彩色数）を満たすグラフ $Gが自明に存在する。一例として、$ 長さが 2 を超える任意のパスが挙げられ、これは 2 色に彩色可能であるが、2 色で調和的な彩色は存在しない。

$χ H (G)$ のいくつかの性質:

\chi _{H}(T_{k,3})=\left\lceil {\frac {3(k+1)}{2}}\right\rceil ,

ここで $T k,3$ は3つのレベルを持つ完全な $k$ 分木である。(Mitchem 1989)

調和的色彩は、HararyとPlantholt（1982）によって初めて提唱されました。しかし、それについてはまだほとんど知られていません。

参照

外部リンク

キース・エドワーズ著『調和的な色彩と無彩色の数に関する書誌』

参考文献

Frank, O.; Harary, F.; Plantholt, M. (1982). 「グラフの線を区別する彩色数」Ars Combin . 14 : 241– 252.
ジェンセン、トミー・R.; トフト、ビャーネ (1995). グラフ彩色問題. ニューヨーク: ワイリー・インターサイエンス. ISBN 0-471-02865-7。
ミッチェム, J. (1989). 「グラフの調和彩色数について」.離散数学. 74 ( 1–2 ): 151–157 . doi : 10.1016/0012-365X(89)90207-0 .