彩色
提供: Mathpedia
定義
- グラフ $G = (V,E)$ と集合 $S$ について、$G$ の $S$-頂点彩色とは、写像 $c\colon V\to S$ であって、隣接する頂点 $x$, $y$ について $c(x) \neq c(y)$ が成り立つようなもののことをいう。
- グラフ $G = (V,E)$ と集合 $S$ について、$G$ の $S$-辺彩色とは、写像 $c\colon E\to S$ であって、隣接する辺 $e$, $f$ について $c(e) \neq c(f)$ が成り立つようなもののことをいう。
information
情報源
- R. Diestel. "Graph Theory". Springer (2000).
