Graph Coloring Games & Drawings

← Back to Domain-Specific Families

Abstractions about adversarial coloring, chromatic bounds, graph drawings, extremal graphs, combinatorial puzzles, and topological covering lemmas.

7 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Goldberg–Seymour Theorem — Every loopless multigraph can be properly edge-colored using no more than the larger of maximum degree plus one and the ceiling of its densest odd-set edge ratio.
• Graph Coloring Game — An adversarial sequential graph-coloring process in which players alternately make legal color assignments, one seeking a complete proper coloring and the other seeking to create an uncolorable position.
• Grundy Number — The largest number of colors that first-fit vertex coloring can be forced to use over all vertex orderings measures a graph's worst-case greedy order sensitivity.
• Knaster–Kuratowski–Mazurkiewicz Lemma — A simplex-covering intersection theorem: if each face is covered by the closed sets indexed by that face’s vertices, then every indexed set shares a common point, converting boundary-compatible local coverage into global coexistence.
• RAC drawing — Represent a graph geometrically so every permitted edge crossing is a two-edge intersection at a right angle, under explicit straight-line or bounded-bend conventions.
• Slitherlink — Select edges of a clue-labeled planar lattice so local face counts and vertex degrees jointly form exactly one nonbranching closed loop.
• Turán Graph — The balanced complete r-partite graph T(n,r), formed by making nearly equal vertex blocks independent and joining every cross-block pair, uniquely maximizing edges among n-vertex graphs with no K_(r+1).