Invariant de graphe

De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes[1] :

• Une propriété est monotone si elle est héritée par les sous-graphes. Le caractère biparti, sans triangle, ou planaire sont des exemples de propriétés monotones.
• Une propriété est héréditaire si elle est héritée par les sous-graphes induits. Toute propriété monotone est donc héréditaire. Le caractère parfait est un exemple de propriété héréditaire non monotone.
• Une propriété est close par mineur si elle est héritée par les mineurs. Le caractère planaire est un exemple de propriété close par mineur.