MathDB
Satisfy edges as much as possible

Source: STEMS 2021 CS Cat B Q1

January 23, 2021
graph theorycombinatorics

Problem Statement

We are given kk colors and we have to assign a single color to every vertex. An edge is satisfied if the vertices on that edge, are of different colors.
[*]Prove that you can always find an algorithm which assigns colors to vertices so that at least k−1k∣E∣\frac{k - 1}{k}|E| edges are satisfied where ∣E∣|E| is the cardinality of the edges in the graph.[/*] [*]Prove that there is a poly time deterministic algorithm for this [/*]
Back to ProblemsView on AoPS