ロバース数

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

与えられた無向グラフ$G\,$に対して定義される数値 ($\vartheta (G)\,$と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. $G\,$のクリーク数$w(G)\,$と彩色数$\chi (G)\,$に対し, $w(G)\leq \vartheta ({\overline {G}})\leq \chi (G)\,$ が成り立つ事が知られている, ただし 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \overline{G}\,} は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G\,} の補グラフである.$w(G),\chi (G)\,$ を求めるのはNP困難であるのに対し, $\vartheta ({\overline {G}})\,$は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.