A graph problem

Revision en1, by virus_1010, 2017-10-07 16:44:22

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English virus_1010 2017-10-07 16:44:22 598 Initial revision (published)