The equivalence relations cover problem (in graph theory)
Although I don't know the name for such problem, I can show this problem is NP-hard.

For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph.

According to this article, finding the chromatic index for a triangle free graph is NP-complete.