Graph Class Map

Relation View

Relation sources

χ-binding function

χ(H) ≤ f(ω(H)) for every nonempty induced subgraph H; write ω = ω(H). Structural bounds and class-dependent constants are fixed uniformly. These are upper bounds; optimality is stated only when verified.

Complexity

Graph problems

ProblemComplexityPaper

Model checking

LogicComplexityPaper