# $k$-coloring problem which minimizes the number of conflicting vertices

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

1. The number of conflicting vertices is minimized instead of the number of conflicting edges.
2. The graph may not be $k$-colorable.

Is there any algorithms that can solve my problem?

• This question seems a little too general? – muzzlator Jun 9 '14 at 16:12
• If you want an answer which works for ALL graphs, the answer is $|V|-k$. – N. S. Jun 9 '14 at 16:16
• For example, if $G$ is complete and $k=\mid V\mid$, then the number you are looking for is $0$. – Jika Jun 9 '14 at 16:16
• I agree - more constraints on $G$ and $k$ are needed to give a satisfying answer. If, for example $G$ is $k$-colorable, then 0 vertices need to be deleted. But if $G$ is a complete graph on more than $k$ vertices, then you must delete $|V(G)|-k$ vertices. – Perry Elliott-Iverson Jun 9 '14 at 16:18