MathCastle
Graph TheoryEasyGraph Coloring

Graph Coloring · Easy problem

Six tasks T0,…,T5T_0,\ldots,T_5 must be scheduled into time blocks. The conflicting pairs (which cannot share a block) are T0&T1T_0\&T_1, T0&T2T_0\&T_2, T1&T2T_1\&T_2, T0&T3T_0\&T_3, T3&T4T_3\&T_4, and T4&T5T_4\&T_5. Using the greedy-coloring bound Δ(G)+1\Delta(G)+1 — without running the algorithm — what is the most blocks this bound could ever force, no matter what order the tasks are colored in?