Hello everyone,
I recently gave this gym contest (virtual) and couldn't come up with a solution to problem G.
The problem is as follows: Given a graph with n ( ≤ 103) nodes and some edges ( ≤ n *(n - 1) / 2). Let's denote m as the maximum degree in the graph. Now you need to color the graph with 2 colors with the constraint that each node can have atmost m / 2 neighbors with the same color as the node itself . Given the above info, give the coloring of the graph.
Please help me solve it.
Thanks.
consider this problem.
you want to split nodes in to two parts such that every node with degree d has at most d / 2 neighbors in the it's part .
Solution : between all ways to split nodes in to two part , consider the way that number of edges between two part is maximum, this way is a good partition. because if we have such a node v with degree d that has more than d / 2 neighbor in ot's side , move this node to other side , now you have a partition with more number of edges , that is not possible !
from this you can make an algorithm for solving problem!