Inductive Graph Invariants and Algorithmic Applications

We introduce and study an inductively defined analogue \(f_{\text {IND}}()\) of any increasing graph invariant f(). An invariant f() is increasing if \(f(H) \le f(G)\) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc into a single generic notion. For any given increasing f(), this gets us several new invariants and many of which are also increasing. It is also shown that \(f_{\text {IND}}()\) is the minimum (over all orderings) of a value associated with each ordering.