Low unsociable sets implies low chromatic number
Source: IMO 2015 Shortlist, C7
July 7, 2016
combinatoricsgraph theoryIMO Shortlist
Problem Statement
In a company of people some pairs are enemies. A group of people is called unsociable if the number of members in the group is odd and at least , and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most unsociable groups, prove that it is possible to partition the company into parts so that no two enemies are in the same part.Proposed by Russia