algorithm - Partially coloring a graph with 1 color -

i started reading graph theory , reading graph coloring. problem popped in mind:

we have color our undirected graph(not completely) 1 color number of colored nodes maximized. need find maximum number. able formulate approach non cyclic graphs :

my approach : first divide graph isolated components , each component. make dfs tree , make 2 dp arrays while traversing root comes last :

dp[0][u]=sum(dp[1][visited children])

dp[1][u]=sum(dp[0][visited children])

ans=max(dp[1][root],dp[0][root])

dp[0][i] , dp[1][i] initialized 0,1 respectively.

here 0 signifies uncolored , 1 signifies colored.

but not work cyclic graphs have assumed no visited children connected.

can guide me in right direction on how solve problem cyclic graphs(not brute force)? possible modify approach or need come different approach? greedy approach coloring nodes least edges work?

this problem np-hard well, , known maximum independent set problem.

a set s<=v said independent set in graph if each 2 vertices u,v in s, there no edge (u,v).

the maximum size of s (which number seeking) called independence number of graph, , unfortunately finding np-hard.

so, unless p=np, algorithm fails general purposes graphs.

---

proving simple, given graph g=(v,e), create complementary graph g'=(v,e') (u,v) in e' if , if (u,v) not in e.

now, given graph g, there clique of size k if , if there independent set of size k in g', using same vertices (since if (u,v) 2 vertices independent set, there no edge (u,v) in e', , definition there edge in e. repeat vertices in independent set, , got clique in g).

since clique problem np-hard, makes 1 such well.