Col

👥 2 players 📍 Indoor📍 Anywhere ⚡ Calm 🧩 Moderate ⏱ 10-30 minutes 🎂 Ages 6+

Quick Pitch

Col (short for "Coloring") is an impartial combinatorial game played on a graph (network of connected points).

Equipment Needed

Sheet of paper
Pencil or pen (two different colors or symbols)
Ruler (helpful for drawing graphs)
Eraser (optional)

Setup

Draw Graph: Create a graph structure
- Vertices: dots/circles
- Edges: lines connecting vertices
- Simple example: Triangle (3 vertices, all connected)
- Complex example: Larger connected network
Standard Starting Graphs:
- Triangle Graph: 3 vertices, all connected
- Square Graph: 4 vertices in square formation
- Wheel Graph: Central vertex connected to ring of vertices
- Complete Graph: Every vertex connected to every other (K₄, K₅, etc.)

Example Triangle Graph:

    A
   / \
  B - C

Assign Colors: Players choose which color they'll use (Red and Blue, X and O, 1 and 2, etc.)
Decide Turn Order: Player 1 goes first

Rules

Objective

Color the last available vertex, leaving opponent unable to move.

Gameplay

Players alternate turns
On each turn, a player colors one uncolored vertex with their color
A vertex can only be colored if:
- It's not already colored
- Its color doesn't match any adjacent vertex's color
Once colored, a vertex's color is permanent

Example Game on Triangle

Initial state: A, B, C uncolored

Player 1: Colors A with Red
    A(R)
   / \
  B - C

Player 2: Colors B with Blue (must differ from A)
    A(R)
   / \
  B(B)- C

Player 1: Colors C with Red (not adjacent to A, different from B)
    A(R)
   / \
  B(B)-C(R)

Game ends. Player 1 made last move, Player 2 cannot move. Player 1 wins.

Winning Condition

Player unable to color any remaining vertex loses. All remaining uncolored vertices have at least one adjacent vertex with their assigned color, blocking all moves.

Expert Player

Tips

Graph Structure Understanding:

Vertex Degree: Vertices with more connections (higher degree) are harder to color
- Vertices with degree < 2: Usually easier to color
- Central vertices (high degree): Strategic importance
Connectivity: Density of edges affects gameplay
- Sparse graphs: More coloring flexibility
- Dense graphs: Fewer valid moves available
Bipartite Graphs:
- If graph is bipartite (can be 2-colored for all vertices), Col becomes different
- First player can usually color one side, second player the other

Strategic Principles:

Control Hubs: Vertices with many connections (hubs) determine game flow
- Color high-degree vertices early
- Control which player accesses satellite vertices
Create Barriers: Color strategically to block opponent's future moves
- Don't randomly color; plan ahead
Force Situations: Restrict opponent to specific vertices
- Color vertices to eliminate opponent's color options
Parity Observation:
- In bipartite graphs, first player colors one partition, second colors other
- Partition size determines winner

Example Strategy on Larger Graph:

Starting 5-vertex wheel graph:

      A
     /|\
    B C D
     \|/
      E

Player 1 should color central hub (E) with their color. This restricts Player 2's options for surrounding vertices, giving Player 1 more control.

Variations

Multi-Color: Use 3+ colors instead of 2 (changes strategy dramatically)
Different Graphs: Play on different graph structures (cycle graphs, path graphs, random graphs)
Larger Graphs: 10+ vertices create more complex games
Restricted Moves: Additional movement restrictions

Learn More — History & Origins

History & Origins

Col is a lesser-known combinatorial game in the Berlekamp-Conway-Guy game theory tradition. It appears in academic papers on impartial games and graph games but lacks the fame of games like Nim or Chomp. Col demonstrates principles of graph coloring — a fundamental problem in mathematics and computer science. The game is studied by combinatorial game theorists but remains relatively obscure in recreational gaming.

Cultural Context

Col appears in academic game theory literature but remains less known in recreational gaming compared to Nim or Chomp. The game demonstrates practical applications of graph theory and strategic thinking.

The game appeals to mathematicians, computer scientists, and graph theory enthusiasts. It shows how abstract mathematical structures (graphs) create interesting games and how coloring problems relate to strategy.

Mathematical Notes

Graph Coloring:

The chromatic number is minimum colors needed for proper coloring
2-colorable graphs (bipartite) have chromatic number 2
Wheel graphs need 3 colors if the wheel has odd number of rim vertices

Game Theory:

Col is an impartial game (both players have same moves available)
Positions can be analyzed using Sprague-Grundy theory
Some positions are winning/losing with perfect play

Small Graph Analysis

Triangle (K₃):

First player wins (colors one vertex, second player colors another with different color, first colors remaining)

Square (C₄):

Both players can color vertices of same color on opposite corners
Second player can force a draw or win

Pentagon (C₅):

Odd cycles have interesting properties
First player advantage in most odd-cycle games

Wheel Graphs:

Center vertex is key strategic position
Color center early to control surroundings

Col