Proposition 3.2, p. 158 — removing consistently precolored lecture-nodes gives Ĝ′: Ĝ has a p-coloring respecting the precoloring iff Ĝ′ is p-colorable
ProvedTimetabling85.CourseColoring.prop_3_2Let be a course scheduling graph: its nodes are lecture-nodes and period-nodes , and all pairs of period-nodes are adjacent. Assume some lecture-nodes have been precoloured: a precoloured node must receive the colour of the period-node . Assume the precolouring is consistent:
- no precoloured node is adjacent to its own period-node , and
- no two adjacent lecture-nodes are precoloured with the colour of the same period-node.
Let be obtained from by removing every precoloured node and linking each of its remaining neighbours with the period-node ; has no precoloured node. Then
For node colouring, unlike edge colouring, preassignments therefore do not make the problem harder: they can be absorbed into the graph.
Formalization Note The consistency hypotheses are an addition to the page, and a necessary one: if two adjacent lecture-nodes are precoloured with the same colour, has no respecting colouring, but removing both deletes the edge between them and may be -colourable (two adjacent lecture-nodes and one period-node, ). The proof on the page also speaks of a 1–1 correspondence between the colourings; with precolours read as fixed absolute colours this fails (colourings of may permute the colours of the period-nodes), so only the equivalence of the proposition is stated. "Precoloured" is read relative to the period-nodes (), as in the proof of Proposition 3.1; since the period-nodes form a clique on nodes, this is equivalent to precolouring with absolute colours up to a permutation of the palette. is any graph with this shape; the graph of Proposition 3.1 is one.
import Mathlib import Definitions.Def_Timetabling85_CourseColoring_CSUP
namespace Timetabling85.CourseColoring
theorem prop_3_2 {V : Type*} {p : ℕ} (H : SimpleGraph (V ⊕ Fin p)) (pc : V → Option (Fin p))
(hclique : ∀ k k' : Fin p, k ≠ k' → H.Adj (Sum.inr k) (Sum.inr k'))
(hcons_period : ∀ (v : V) (k : Fin p), pc v = some k → ¬ H.Adj (Sum.inl v) (Sum.inr k))
(hcons_lecture : ∀ (v v' : V) (k : Fin p), pc v = some k → pc v' = some k →
¬ H.Adj (Sum.inl v) (Sum.inl v')) :
(∃ c : H.Coloring (Fin p), ∀ (v : V) (k : Fin p), pc v = some k →
c (Sum.inl v) = c (Sum.inr k)) ↔
(removePrecolored H pc).Colorable p := by sorry
end Timetabling85.CourseColoring
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.