ロバース数

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