ロバース数

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

与えられた無向グラフ$G\,$に対して定義される数値 ($\vartheta (G)\,$と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. $G\,$のクリーク数構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w(G)\,} と彩色数$\chi (G)\,$に対し, 構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w(G)\leq \vartheta ({\overline {G}})\leq \chi (G)\,} が成り立つ事が知られている, ただし ${\overline {G}}\,$ は$G\,$の補グラフである.構文解析に失敗 (Conversion error. Server ("https://en.wikipedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle w(G),\chi (G)\,} を求めるのはNP困難であるのに対し, $\vartheta ({\overline {G}})\,$は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.