【ろばーすすう (Lov\'asz number)】
与えられた無向グラフ G {\displaystyle G\,} に対して定義される数値 ( ϑ ( G ) {\displaystyle \vartheta (G)\,} と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. G {\displaystyle G\,} のクリーク数 w ( G ) {\displaystyle w(G)\,} と彩色数 χ ( G ) {\displaystyle \chi (G)\,} に対し, w ( G ) ≤ ϑ ( G ¯ ) ≤ χ ( G ) {\displaystyle w(G)\leq \vartheta ({\overline {G}})\leq \chi (G)\,} が成り立つ事が知られている, ただし G ¯ {\displaystyle {\overline {G}}\,} は G {\displaystyle G\,} の補グラフである. w ( G ) , χ ( G ) {\displaystyle w(G),\chi (G)\,} を求めるのはNP困難であるのに対し, ϑ ( G ¯ ) {\displaystyle \vartheta ({\overline {G}})\,} は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.
に対して定義される数値 (
と書かれる事が多い)で, グラフのクリーク数および彩色数と重要な関連をもつ. のクリーク数
と彩色数
に対し, 
が成り立つ事が知られている, ただし 
はの補グラフである.
を求めるのはNP困難であるのに対し, 
は多項式時間で求めることができる. 頂点に重みのついたグラフにも, 自然な形で定義を拡張することができる.