ロバース数

出典: ORWiki

【ろばーすすう (Lovász number)】

与えられた無向グラフ $G\,$ に対して定義される数値 ( $\vartheta (G)\,$ と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. $G\,$ のクリーク数 $w(G)\,$ と彩色数 $\chi (G)\,$ に対し, $w(G) \leq \vartheta (\overline{G}) \leq \chi (G)\,$ が成り立つ事が知られている, ただし $\overline{G}\,$ は $G\,$ の補グラフである. $w(G), \chi (G)\,$ を求めるのはNP困難であるのに対し, $\vartheta (\overline{G})\,$ は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.