Vertex cover in conflict graphs

We study a graph class called conflict graph, which is a union of a finite number of given forests of complete multipartite graph. It is interesting that conflict graph can model many natural problems, such as in database application and others. We show that this property is non-trivial if limiting the number of forests of complete multipartite graph. Then study the problem of vertex cover on conflict graph in this paper. The results list as follows, if the number of forests of complete multipartite graph is fixed, conflict graph is non-trivial property, but finding 1.36-approximation algorithms is NP-hard. Also given 2 forests of complete multipartite graph and maximum degree less than 7, vertex cover problem of conflict graph is NP-complete. Moreover, it is shown to be NP-hard to find an algorithm for vertex cover of conflict graph within [Formula presented], for any ε>0, if there is no the degree restriction over the graph. At last, we design an approximation algorithm for the conflict graph consisting of r forests of complete multipartite graph and show that the approximation ratio can be bounded by [Formula presented] and it's near optimal.