ロバース数

【ろばーすすう (Lov\'asz 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})$は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.