ON THE EQUIVALENCE COVERING NUMBER OF SPLITGRAPHS

An equivalence graph is a disjoint union of cliques. For a graph G let eq(G) be the minimum number of equivalence subgraphs of G needed to c over all edges of G. We call eq(G) the equivalence covering number of G. It was shown in [8] that computing the equivalence covering number is NP-hard, even when restricted to graphs in which no two triangles h ave a vertex in common. We show that the equivalence covering number f or splitgraphs can be approximated within an additive constant 1. We a lso show that obtaining the exact value of the equivalence number of a splitgraph is an NP-hard problem. Using a similar method we also show that it is NP-complete to decide whether the equivalence covering num ber of a graph is 3, even for graphs with maximum degree 6 and with ma ximum clique number 4.