Graph theory

Notations

NotationMeaning
nnNumber of vertices
mmNumber of edges
χ(G)\chi(G)Chromatic number
ω(G)\omega(G)Clique number
ϑ(G)\vartheta(G)Lovasz number

Random graphs

1≤χ(G)≤n1 \leq \chi(G) \leq n

χ(G)(χ(G)−1)≤2m\chi(G)(\chi(G)-1) \leq 2m

χ(G)≥ω(G)\chi(G) \geq \omega(G)

χH(G)≤χV(G)≤ϑ(G)≤χf(G)≤χ(G)\chi_H(G) \leq \chi_V(G) \leq \vartheta(G) \leq \chi_f(G) \leq \chi(G)

Perfect graphs

χ(G)=ω(G)\chi(G) = \omega(G)