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.

• NP-completenessBroader topic: Deciding whether a graph can be colored with three colors is NP-complete.

• 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.

• Edge coloringCompared with: It colors vertices rather than edges, though both problems forbid equal colors across adjacency.

• Four color theoremNarrower topic: The theorem is a universal upper bound on the number of colors needed.

• Chromatic numberNarrower topic: Chromatic number is the minimum color count in the vertex-coloring version of this broader problem.

• 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.

• Brooks' theoremNarrower topic: Brooks' theorem bounds the minimum number of colors needed for a proper vertex coloring.

• 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.

• Courcelle's theoremBroader topic: For fixed numbers of colors, existence of a proper coloring is expressible in the theorem's logic.

• Erdős–Faber–Lovász conjectureNarrower topic: The conjecture asks whether the union can always be colored using at most n colors.

• Five color theoremNarrower topic: The theorem is a universal upper bound for vertex coloring on planar graphs.

• Heawood conjectureNarrower topic: The conjecture bounds the colors required for graphs constrained by a surface.

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

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

• De Bruijn–Erdős theorem (graph theory)Narrower topic: The theorem concerns when a coloring with a fixed finite palette exists.

• Grötzsch's theoremNarrower topic: The theorem guarantees a three-coloring for a restricted class of graphs.

• Hedetniemi's conjectureNarrower topic: The conjecture compares the minimum numbers of colors needed before and after taking a product.

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