Minor Of A Signed Graph
A minor of a given a signed graph (G, 𝛴 ) is any signed graph obtained by (possibly repeated) use of the following operations in any order.
- delete a vertex
- delete an edge
- contract a positive edge
- resign
It follows that balance of a cycle cannot be altered by contracting edges or resigning. Though it may no longer be a cycle by deleting an element or by contracting a chord. This is the key tool which provide stronger connection between minor and homomorphisms.
It is of interest to check that (G, E(G)) has no (K3, E(K3)) if and only if G is a bipartite graph.
An odd-K4 is a subdivision of a K4 where each of the triangles has become an odd cycle.
It can be checked that given a graph G, (G, E(G)) has no (K4, E(K4))-minor if an only if G has not odd-K4 as a subgraph.
Extending on this terminology, given a graph G the notation odd- Kn free or odd- Kn minor-free is used when (G, E(G)) has no (Kn, E(Kn))-minor.