Linked from

The 30 pages that link to Graph coloring, each with the reason it gives.

• Graph theoryRelated: Coloring turns adjacency constraints into questions about the minimum resources required.

• Bipartite graphRelated: A graph is bipartite exactly when its vertices can be properly colored with two colors.

• Complete graphRelated: A complete graph on n vertices requires n distinct colors.

• Graph (discrete mathematics)Related: It models resource assignments where connected entities cannot share a resource.

• Vertex (graph theory)Related: A vertex's color is constrained by the colors of its neighbors.

• Constraint satisfaction problemRelated: It models map coloring and frequency assignment as pairwise constraints.

• Degree (graph theory)Related: Maximum degree bounds the number of colors needed by a basic greedy coloring.

• Simple graphRelated: Simple graphs commonly encode conflicts whose endpoints must receive different colors.

• Odd cycleRelated: An odd cycle requires three colors for a proper vertex coloring.

• Partition of a setRelated: Color classes form a partition of vertices when empty classes are omitted.

• Induced subgraphRelated: Coloring behavior on induced subgraphs helps characterize perfect graphs.

• Register allocationRelated: Register assignment can be modeled as coloring an interference graph with registers as colors.

• Graph homomorphismRelated: A proper coloring is exactly a homomorphism to a complete graph.

• Pólya enumeration theoremRelated: Symmetry-aware variants count colorings only once when graph automorphisms relate them.

• Lovász local lemmaRelated: Coloring proofs encode local violations as events and use the lemma to avoid them.

• Intersection graphRelated: For intersection graphs, coloring assigns distinct resources to objects that overlap.

• Algebraic combinatoricsRelated: Chromatic polynomials and related algebraic tools count valid colorings.

• Teichmüller–Tukey lemmaRelated: Finite-character arguments can extend partial colorings when every finite subgraph admits a coloring.