ロバース数

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

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