Clique number ω(G): size of largest complete subgraph. ω(K_n)=n, ω(bipartite)≤2, ω(Petersen)=2. Always ω(G)≤χ(G). Perfect graphs: ω=χ. ω(G)=α(Ḡ) by complement. Finding maximum clique is NP-hard.
How to Use
Select graph:
- ω(G): Clique number
- Clique: Example max clique
- χ bound: ω≤χ
Perfect Graphs
In perfect graphs, ω(G)=χ(G) for every induced subgraph. The Strong Perfect Graph Theorem (2006): G is perfect iff no odd hole or odd antihole induced subgraph. For perfect graphs, ω can be computed in polynomial time!
Algorithms
Exact: Bron-Kerbosch with pivoting O*(3^{n/3}). Approximate: greedy and local search. For special classes (chordal, perfect): polynomial. For general graphs: one of the hardest problems in computational complexity.
Step-by-Step Instructions
- 1Select graph.
- 2Compute ω(G).
- 3See max clique.
- 4Compare to χ.
- 5Check complement.