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 . Department Y's conflict graph is a -course cycle (each course conflicts with exactly two others, forming a ring), giving it chromatic number . Treating both departments together as one scheduling problem, what is the fewest exam slots needed overall?