MathCastle
Graph TheoryMediumGraph Coloring

Graph Coloring · Medium problem

Two university departments schedule exams completely independently (no student takes courses in both). Department X's conflict graph is a triangle with two extra courses each conflicting only with ONE triangle course (the same one), giving it chromatic number 33. Department Y's conflict graph is a 66-course cycle (each course conflicts with exactly two others, forming a ring), giving it chromatic number 22. Treating both departments together as one scheduling problem, what is the fewest exam slots needed overall?