subgraph_isomorphisms for considering absent edge

Yes, you can achieve the same by using an appropriate domains argument. For each vertex, give the list of other vertices with the same colour. See the documentation for details. I’m sorry, I don’t have time to write an example now.