04-BS-16 · December 2013

Question 12 of 12: Chromatic Number and Graph-Colouring Scheduling

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 12: Chromatic Number and Graph-Colouring Scheduling (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $K_n$ and $K_{m,n}$ (parts a). A conflict graph on 7 courses with the 16 listed edges (part b) — an edge means the two courses cannot share a time slot.

Find. (a) The two chromatic-number formulas. (b) The minimum number of time slots (= chromatic number of the conflict graph) and a valid assignment.

(a-i) $\chi(K_n)$. Every pair of vertices in $K_n$ is adjacent, so all $n$ vertices need pairwise-distinct colours, and $n$ colours obviously suffice: $\boxed{\chi(K_n)=n}$.
(a-ii) $\chi(K_{m,n})$. $K_{m,n}$ is bipartite with at least one edge (for $m,n\ge1$): colour one side entirely colour 1, the other entirely colour 2 — no edge exists within a side, so this is proper: $\boxed{\chi(K_{m,n})=2}$.
(b) Find a clique to lower-bound $\chi$. Check courses $\{1,2,3,4\}$: edges $\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$ are ALL present in the conflict list — $\{1,2,3,4\}$ is a 4-clique (every pair conflicts), so all four need different slots: $\boxed{\chi\ge4}$.
(b) Construct a proper 4-colouring. Fix $1{=}A,2{=}B,3{=}C,4{=}D$ (forced distinct by the clique). Course 7 conflicts with $1,2,3$ (all of $A,B,C$), so $7=D$. Course 5 conflicts with $2(B),4(D),7(D)$, leaving $\{A,C\}$; course 6 conflicts with $3(C),4(D),7(D)$, leaving $\{A,B\}$; and $5$-$6$ also conflict, so pick $5=C,6=A$ (distinct, and both satisfy their remaining constraints). Checking every one of the 16 listed conflict pairs against $\{1{=}A,2{=}B,3{=}C,4{=}D,5{=}C,6{=}A,7{=}D\}$ confirms no conflicting pair shares a colour.
(b) Conclusion. A valid 4-colouring exists and 4 is the lower bound from the clique, so $$\boxed{\chi=4\text{ time slots.}}$$ Schedule: Slot $A=\{1,6\}$, Slot $B=\{2\}$, Slot $C=\{3,5\}$, Slot $D=\{4,7\}$.

Final results — Question 12
Part	Result
(a-i) $\chi(K_n)$	$n$
(a-ii) $\chi(K_{m,n})$	2
(b) Minimum time slots	4
(b) Schedule	Slot 1: {1,6}; Slot 2: {2}; Slot 3: {3,5}; Slot 4: {4,7}

Topic: Graph colouring as exam/resource scheduling; clique number as a chromatic-number lower bound.

Key relations: $\chi(G)\ge\omega(G)$ (clique number) always; finding a $k$-clique proves $\chi\ge k$; exhibiting a proper $k$-colouring proves $\chi\le k$ — together they pin down $\chi$ exactly, as here ($\omega=4$ and a valid 4-colouring both found).

Why this works: Courses that pairwise share students form a "conflict graph" where a proper colouring is exactly a valid exam schedule (same colour = same time slot, and no two same-coloured courses conflict). Finding the 4-clique $\{1,2,3,4\}$ immediately rules out 3 slots being enough, and then a direct constructive colouring (propagating forced colours outward from the clique) confirms 4 is also achievable.

Common pitfall: Assuming $\chi=\Delta+1$ (max degree + 1) is always tight — it is only an upper bound (Brooks' theorem gives a tighter bound for most graphs); missing that courses 5 and 6 are ALSO directly in conflict with each other when assigning their colours.

Source: Rosen, Discrete Mathematics and Its Applications, §10.8 (graph colouring and applications).

← Question 11 Back to the paper →