MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

A review committee has reviewers 1,2,3,4,51,2,3,4,5. Reviewers 1,2,31,2,3 all conflict with one another (edges 12,13,2312,13,23), reviewer 44 conflicts only with reviewer 11 (edge 1414), and reviewer 55 conflicts only with reviewer 22 (edge 2525). A schedule with kk time slots assigns each reviewer to one of the kk slots so that no two conflicting reviewers share a slot. What is the smallest kk for which at least 200200 different valid schedules exist?