All graphs are undirected and have no parallel edges/loops. All nodes have a "color" attribute.

Given two graphs G_host and G_motif, find a set of node sets ({N1, N2, ...} where Ni is a set of nodes) of G_host such that:

1. for every Ni, a subgraph of G_host can be constructed such that it is isomorphic to G_motif (the subgraph can be non-induced);
2. if i!=j, then Ni and Nj are disjoint (do not intersect);
3. the number of node sets is maximized.

Here is an example, let the motif be blue-red, and the host be

        1blue
        |
2blue - 3red - 4blue - 6red
        |
        5blue

What we want is {{1,3}, {4,6}}, or {{3,5}, {4,6}} or {{2,3}, {4,6}}. Just need to find one of the three.

For small G_host I can just find all subgraph monomorphisms then find mutually disjoint node sets, but it's getting too expensive even for G_host with a few hundred nodes. Is there a way to solve this without finding all subgraph monomorphic mappings?