数学 › グラフ理論 › 彩色

縮退数・彩色数(coloring number)

定義 2.2(「彩色」§2)

GG の空でないどの部分グラフ HH も次数 kk 以下の頂点をもつとき、GG は kk-縮退であるという。max⁡H⊆Gδ(H)\max_{H\subseteq G}\delta(H)(HH は空でない部分グラフを動く)を GG の縮退数、それに 1 を足した数を col⁡(G)\operatorname{col}(G) と書く。

本文で読む(前後の説明と例)→

閉包の状態

定義

定義は閉包の起点です(証明を要しません)。

印の意味: ✓公理まで証明済み ・ △証明あり(閉包未完)・ ※主張のみ。テーマごとの集計は 閉包の状況。

これを使っている定理

証明で明示的に参照している定理は、まだありません。

関連するノック 1 問