AI Glossary / Graphs and symbolic AI / Intermediate

Graph coloring

Definition

Graph coloring assigns labels, traditionally called colors, to graph elements under specified compatibility rules. The usual vertex-coloring problem assigns a color to every vertex so adjacent vertices have different colors. When the aim is to use as few colors as possible, the smallest feasible number is the graph's chromatic number.

What it means

Colors are abstract labels and need not be visual colors. In a conflict graph, vertices can represent tasks and an edge can mean that two tasks cannot share a time slot. Assigning different colors to adjacent vertices then models a simple scheduling restriction.
The intended variant matters. Vertex coloring differs from edge coloring, which labels edges under its own rules. A proper coloring merely satisfies the adjacency restrictions; a minimum coloring also proves that no smaller palette works. A heuristic can produce a proper coloring without proving it uses the fewest colors.

How it works

Construct a graph whose edges accurately encode the conflicts. Choose the allowed colors, or search for a small palette. A greedy vertex-coloring method processes vertices in an order and assigns each an available color not used by its already colored neighbors.
The order affects the result. Exact methods may use backtracking, constraint programming, or other combinatorial techniques to determine whether a smaller palette is feasible. Verification of a completed coloring is straightforward: inspect every edge and check that its endpoints differ. Finding or proving an optimal coloring is a different and generally harder task.

Three practical examples

• A small examination-scheduling model assigns different time slots to exams that share students.
• A compiler-related teaching exercise represents conflicting live values and studies assignments to a limited set of registers.
• A map-coloring puzzle labels neighboring regions differently, using a graph to separate adjacency rules from the drawing.

Think of it this way

Think of assigning meeting slots so any two meetings with a shared participant occur at different times. This captures pairwise conflict coloring. The analogy is limited because real schedules may include durations, availability, room capacities, and preferences that a simple graph coloring does not represent.

Worked example

Take the path A-B-C-D, with edges AB, BC, and CD. A valid two-color assignment is A red, B blue, C red, and D blue. At least two colors are necessary because the graph has an edge, so this assignment proves the chromatic number is 2.
Now apply a greedy rule that uses the first available color, processing vertices in the order A, D, B, C. A receives red. D is not adjacent to A, so it also receives red. B sees red on A and receives blue. C is adjacent to both B and D, so it sees blue and red and receives a third color, green.
The resulting coloring is proper, but it is not minimum. The same graph supports the two-color assignment already shown. This example isolates the effect of vertex ordering without requiring a large or difficult graph.

Illustrative case study

In a fictional workshop scheduler, the Maple team uses greedy coloring to assign sessions to time slots. A four-session example receives three slots, which the team initially treats as a minimum requirement. A reviewer provides the two-slot pattern from the worked example.
The team changes its report to distinguish a feasible assignment from a proved minimum. It also checks whether additional availability restrictions were omitted from the conflict graph. The invented case demonstrates algorithmic and modeling limitations, not a claim that a particular scheduling tool wastes resources in practice.

Common misconceptions and mistakes

Do not assume a coloring is optimal because every adjacent pair differs. That proves feasibility only. Do not assume that nonadjacent vertices must share a color; they are allowed to differ even when no edge forces it.
The four-color theorem concerns planar maps under the corresponding graph conditions, not arbitrary conflict graphs. A clique of k vertices requires at least k colors, but the absence of a large clique does not by itself establish a matching upper bound. Self-loops also require special attention: under ordinary proper vertex coloring, a vertex cannot have a color different from itself.

Business use

Graph coloring is useful when a business problem can be expressed as pairwise incompatibilities and interchangeable resource labels. It offers a compact model and a simple way to check an assignment's basic feasibility.
Before applying it, confirm that conflicts are accurately represented and that colors correspond to genuinely interchangeable options. If tasks have different durations or resources have different capabilities, additional constraints may be required. Report whether the method found a feasible palette size or proved the minimum, and avoid translating a heuristic result into a claimed unavoidable resource requirement.

People also ask

Must the colors be literal colors?

No. They can represent slots, channels, or other labels.

Does a greedy algorithm always find the chromatic number?

No. The worked example shows a proper three-color result for a graph that needs only two.

Can disconnected components reuse colors?

Yes. With no edges between them, ordinary vertex coloring permits the same palette across components.

Check your understanding

Why is the greedy three-color result for A-B-C-D not evidence that three colors are necessary?

Answer: A valid two-color assignment exists, so three cannot be the minimum. The greedy result reflects its ordering and local choices, not a proof excluding all two-color assignments.

Related terms

• Greedy algorithms
• Constraint satisfaction
• Chromatic number
• proper coloring
• conflict graph
• greedy algorithm
• clique
• edge coloring
• planar graph

Learn next

Learn next about graph-coloring bounds. Add edge DA to the path and check that two colors still work. Then add diagonal AC and identify a three-vertex clique that forces a third color. Separate the lower-bound argument from the construction of a valid coloring.

More in Graphs and symbolic AI

• Grammar - A grammar is a formal description of how valid expressions can be structured in a language.
• Graph - A graph is a mathematical structure made of vertices, also called nodes, and edges that represent relationships between them.
• Graph clustering - Graph clustering groups data points represented as nodes of a graph using the relationships encoded by its edges.
• Graph Convolutional Network - A Graph Convolutional Network, or GCN, is a neural-network architecture that learns representations using a graph's connections together with features...
• Graph Convolutional Policy Network - Graph Convolutional Policy Network, or GCPN, is a model introduced for goal-directed graph generation using reinforcement learning.
• Graph Hashing - Graph hashing converts a graph's selected structural and attribute information into a compact identifier.

Sources

NetworkX official greedy-color documentation, strategy-dependent vertex ordering: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.coloring.greedy_color.html Russell and Norvig, original search chapter, map-coloring problem formulation: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf

Previous: Graph Coarsening Algorithm Next: Graph Convolutional Network