Graph minor
Parity conditions

An alternative and equivalent definition of a graph minor is that H is a minor of G whenever the vertices of H can be represented by a collection of vertex-disjoint subtrees of G, such that if two vertices are adjacent in H, there exists an edge with its endpoints in the corresponding two trees in G.An odd minor restricts this definition by adding parity conditions to these subtrees. If H is represented by a collection of subtrees of G as above, then H is an odd minor of G whenever it is possible to assign two colors to the vertices of G in such a way that each edge of G within a subtree is properly colored (its endpoints have different colors) and each edge of G that represents an adjacency between two subtrees is monochromatic (both its endpoints are the same color). Unlike for the usual kind of graph minors, graphs with forbidden odd minors are not necessarily sparse. The Hadwiger conjecture, that k -chromatic graphs necessarily contain k -vertex complete graphs as minors, has also been studied from the point of view of odd minors.

A different parity-based extension of the notion of graph minors is the concept of a bipartite minor, which produces a bipartite graph whenever the starting graph is bipartite. A graph H is a bipartite minor of another graph G whenever H can be obtained from G by deleting vertices, deleting edges, and collapsing pairs of vertices that are at distance two from each other along a peripheral cycle of the graph. A form of Wagner's theorem applies for bipartite minors: A bipartite graph G is a planar graph if and only if it does not have the utility graph K as a bipartite minor.
detectable_content:number_placeholders[7]