Classical $k$-coloring problem (k-GCP) is to assign a color selected from $k$ colors to each vertex of graph $G$ so that the number of conflicting edges (the edges with same color endpoints) is minimized. I am interested in the algorithms that obtain the largest subset of vertices that are legal colored.
Two major differences of my problem
- The number of conflicting vertices is minimized instead of the number of conflicting edges.
- The graph may not be $k$-colorable.
Is there any algorithms that can solve my problem?