Zykov's construction, interval graphs and their properties.

Zykov's Construction (!!!)

Since for any graph G, χ(G) ≥ ω(G), Zykov's construction shows that this gap can be arbitrarily large. We iteratively construct graphs G₃, G₄, … such that for every k, χ(Gₖ) = k and ω(Gₖ) = 2. Let G₃ be a 5-cycle. For any k ≥ 3, the construction of Gₖ₊₁ from Gₖ is as follows: Let H₁, H₂, …, Hₖ be k vertex-disjoint copies of Gₖ with no edges between them. Construct a disjoint set S of vertices, one for every possible combination of choosing one vertex from each Hᵢ. Each vertex in S is connected only to the k vertices in the combination it represents. There are no edges between vertices in S.

Zykov's Construction — Vertex Count Example (!!!)

G₃ is a 5-cycle, so it has 5 vertices. When constructing G₄ from G₃: We take k = 3 copies H₁, H₂, H₃ of G₃, giving 3 × 5 = 15 vertices. S contains one vertex for every combination of one vertex from each Hᵢ, giving 5³ = 125 vertices in S. G₄ has 15 + 125 = 140 vertices total.

Interval Graphs (!!!)

An interval graph is a graph whose vertices are closed finite intervals on the real number line, where two vertices are adjacent if and only if their corresponding intervals intersect.

Interval Graph Properties

For any interval graph G, χ(G) = ω(G). This is proven by ordering the vertices by their left endpoints and applying the greedy coloring algorithm. If the greedy algorithm uses m colors on some vertex, then m intervals all mutually intersect at that point, forming a clique of size m. An interval graph cannot contain an induced cycle of length ≥ 4. In other words, every induced cycle in an interval graph must be a triangle (C₃)