{ "id": "ep8nkr0m5z", "slug": "vertex-coloring", "title": "Vertex coloring", "updated": "2026-09-30", "topic_path": [ { "id": "physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical" }, { "id": "physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math" }, { "id": "physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete" }, { "id": "physical.math.discrete.discrete", "label": "General discrete mathematics and discrete structures", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete" }, { "id": "physical.math.discrete.discrete.graph-theory", "label": "Graph theory", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.graph-theory" }, { "id": "physical.math.discrete.discrete.graph-algorithms", "label": "Computational graph problems and algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.graph-algorithms" }, { "id": "physical.math.discrete.discrete.graph-algorithms.graph-coloring-algorithms", "label": "Graph coloring algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete.discrete.graph-algorithms.graph-coloring-algorithms" } ], "geo": [ { "id": "geo.nongeo.t1800.physical.math", "label": "Non-geographic · 1800 to 1945: Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical.math", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1800", "label": "Non-geographic · 1800 to 1945", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800" }, { "id": "geo.nongeo.t1800.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical" }, { "id": "geo.nongeo.t1800.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1800.physical.math" } ] }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.physical", "label": "Physical world and mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical" }, { "id": "geo.nongeo.t1946.physical.math", "label": "Mathematics and statistics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math" }, { "id": "geo.nongeo.t1946.physical.math.discrete", "label": "Logic and discrete mathematics", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete" } ] } ], "excerpt": "Vertex coloring is a graph algorithm assigning colors to vertices so adjacent vertices differ, minimizing colors used; it is NP-complete and models scheduling, register allocation, and frequency assignment.", "snippet": "Vertex coloring is a graph algorithm assigning colors to vertices so adjacent vertices differ, minimizing colors used; it is NP-complete and models scheduling, register allocation, and frequency assignment.", "node": "physical.math.discrete.discrete.graph-algorithms.graph-coloring-algorithms", "markdown": "# Vertex coloring\n\nVertex coloring is a graph algorithm that assigns a color to each vertex of an undirected graph so that adjacent vertices receive different colors, with the number of colors kept as small as possible. Formally, given a graph \\( G=(V,E) \\), the Vertex Coloring Problem requires a color for every vertex such that colors on adjacent vertices differ and the number of colors used is minimized.[1](https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2009.00696.x) A proper \\( k \\)-coloring uses at most \\( k \\) colors, and the chromatic number \\( \\chi(G) \\) is the smallest \\( k \\) for which such a coloring exists.[2](https://www.cs.uleth.ca/~morris/Combinatorics/html/sect_colouring-Vertices.html) The problem is NP-complete[3](https://reference-global.com/download/article/10.2478/v10209-011-0012-y.pdf), yet it models scheduling, timetabling, register allocation, frequency assignment, and communication networks.[1](https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2009.00696.x)\n\n| Key fact | Detail |\n|---|---|\n| Output | A proper coloring: adjacent vertices get different colors; \\( \\chi(G) \\) is the minimum number of colors[2](https://www.cs.uleth.ca/~morris/Combinatorics/html/sect_colouring-Vertices.html) |\n| Complexity | Deciding \\( k \\)-colorability is NP-complete for every fixed \\( k \\ge 3 \\); deciding 1-colorability and 2-colorability is polynomial |\n| Universal bound | Greedy coloring always uses at most \\( \\Delta(G)+1 \\) colors[4](https://iuuk.mff.cuni.cz/~ipenev/KG2S2022Lecture06.pdf) |\n| Exact-method scale | Branch-and-bound handles graphs up to about 80 vertices; some 125-vertex instances remain unsolved optimally[5](https://ar5iv.labs.arxiv.org/html/2206.13678) |\n| Standard benchmark | 137 DIMACS instances; the best SAT-based solver currently solves 94 of them[6](https://arxiv.org/html/2504.04821) |\n| Main applications | Timetabling, register allocation, train platforming, frequency assignment, and communication networks[1](https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2009.00696.x) |\n\n## How it works\n\nThe decision form, \"Is \\( G \\) \\( k \\)-colorable?\", is NP-complete[7](https://www.or.uni-bonn.de/~held/hausdorff_school_22/slides/GraphColoringFormulations.pdf), a result established in [Richard M. Karp](https://www.edgepedia.org/richard-m-karp)'s 1972 paper *Reducibility among Combinatorial Problems*.[8](https://doi.org/10.1007/978-1-4684-2001-2_9) Approximation is also hard: it is NP-hard to approximate \\( \\chi(G) \\) within a factor \\( n^{1-\\epsilon} \\) for all \\( \\epsilon > 0 \\)[6](https://arxiv.org/html/2504.04821), and even finding a coloring with no more than twice the optimal number of colors is NP-hard.\n\nStructural results bound the answer from above. [Greedy coloring](https://www.edgepedia.org/greedy-coloring) with any vertex order produces a proper coloring with at most \\( \\Delta(G)+1 \\) colors, where \\( \\Delta(G) \\) is the maximum degree, so \\( \\chi(G) \\le \\Delta(G)+1 \\).[4](https://iuuk.mff.cuni.cz/~ipenev/KG2S2022Lecture06.pdf) Equality holds only for complete graphs and odd cycles; Brooks' theorem states that every other connected graph satisfies \\( \\chi(G) \\le \\Delta(G) \\).[2](https://www.cs.uleth.ca/~morris/Combinatorics/html/sect_colouring-Vertices.html) • [4](https://iuuk.mff.cuni.cz/~ipenev/KG2S2022Lecture06.pdf) Some cases are polynomial: a connected 2-colorable (bipartite) graph is colored with 2 colors by breadth-first search[9](https://salil.seas.harvard.edu/file_url/439), and a graph is perfect, meaning \\( \\chi(H) \\) equals the largest clique size for every induced subgraph \\( H \\), exactly when no induced subgraph is an odd cycle of length at least 5 or the complement of one.[2](https://www.cs.uleth.ca/~morris/Combinatorics/html/sect_colouring-Vertices.html)\n\n## How it is done\n\n**Greedy and ordered greedy.** The greedy (sequential) algorithm considers vertices one by one and assigns the first available color; it runs in \\( O(n+m) \\) time on a graph with \\( n \\) vertices and \\( m \\) edges.[10](https://ar5iv.labs.arxiv.org/html/1505.05825) Ordering matters. Largest-first orders vertices by non-increasing degree and yields the bound \\( \\chi(G) \\le 1 + \\max_{i} \\min\\{\\deg v_{i},\\, i-1\\} \\), which is sometimes better than \\( 1+\\Delta \\).[10](https://ar5iv.labs.arxiv.org/html/1505.05825) Smallest-last ordering repeatedly removes a minimum-degree vertex and colors in reverse removal order, giving \\( \\chi(G) \\le \\mathrm{dgn}(G)+1 \\), where \\( \\mathrm{dgn}(G) \\) is the degeneracy; it colors any planar graph with six colors.[10](https://ar5iv.labs.arxiv.org/html/1505.05825) Greedy's worst case is poor: a bad order spends \\( n/2 \\) colors on a 2-colorable crown graph, and the gap between the worst-case greedy count (the Grundy number) and \\( \\chi(G) \\) can be arbitrarily large.[10](https://ar5iv.labs.arxiv.org/html/1505.05825) • [11](https://www.sciencedirect.com/science/article/abs/pii/S0305054824001758)\n\n**Exact methods.** Exact algorithms divide into dynamic programming (exponential \\( O(2^{|V|}) \\) space, of theoretical interest only), branch-and-bound enumeration (polynomial space, applicable up to about 80 vertices), and ILP-based algorithms, which are the most efficient for large instances.[5](https://ar5iv.labs.arxiv.org/html/2206.13678) The DSATUR-based branch-and-bound family branches on vertices ordered by saturation degree, the number of distinct colors already present among a vertex's neighbors.[3](https://reference-global.com/download/article/10.2478/v10209-011-0012-y.pdf) State-of-the-art ILP models include assignment-based, partial-ordering, representatives, set-covering and set-partitioning, and OBDD-based models; independent-set-based models give stronger lower bounds, but assignment and partial-ordering models have far fewer variables and win on sparse graphs.[5](https://ar5iv.labs.arxiv.org/html/2206.13678)\n\n**Heuristics for large graphs.** Beyond greedy, DSATUR and Recursive Largest First (RLF) use refined dynamic rules to pick the next vertex to color. [Simulated annealing](https://www.edgepedia.org/simulated-annealing) and tabu search were among the first local search methods applied successfully, and population-based memetic algorithms are among the most effective. Greedy-plus-tabu methods scale to very large graphs and do well on sparse instances but struggle with large dense ones.[12](https://dl.acm.org/doi/fullHtml/10.1145/3603112)\n\n## Origin\n\nThe problem descends from the four-color question posed on October 23, 1852, when Francis Guthrie asked his brother Frederick to put to [Augustus De Morgan](https://www.edgepedia.org/augustus-de-morgan) the question of whether four colors suffice for any map.[13](https://www.ams.org//journals/notices/202206/noti2490/noti2490.html) The proof divided the problem into many subclasses of maps and used a computer algorithm to check four-colorability in all possible cases.[14](https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-11-1.pdf) • [3](https://reference-global.com/download/article/10.2478/v10209-011-0012-y.pdf) On the computational side, Richard M. Karp's 1972 paper *Reducibility among Combinatorial Problems* placed coloring among the classical NP-complete problems[8](https://doi.org/10.1007/978-1-4684-2001-2_9), and [Gregory Chaitin](https://www.edgepedia.org/gregory-chaitin)'s work on register allocation and spilling via graph coloring, published in 2004 in *ACM SIGPLAN Notices*, made coloring a standard compiler technique.[15](https://doi.org/10.1145/989393.989403)\n\n## Variants\n\n**Equitable coloring** requires that any two color classes differ in size by at most one, with the equitable chromatic number defined analogously.[16](https://link.springer.com/rwe/10.1007/978-1-4614-6624-6_25-1) Applications include scheduling in communication systems, construction timetables, mutual exclusion scheduling, and round-a-clock scheduling.[17](https://ar5iv.labs.arxiv.org/html/2504.14711)\n\n**Preference and list models** extend the basic problem for scheduling: list-coloring, mixed graph coloring, co-coloring, coloring with preferences, and bandwidth coloring address increasingly complex timetabling and scheduling settings.[18](https://www.gerad.ca/~alainh/G1384.pdf) In the preference model, a classical result of Cartwright and Harary states that a vertex-coloring satisfying all preferences exists if and only if the graph contains no cycle with exactly one strong edge.[18](https://www.gerad.ca/~alainh/G1384.pdf) Equitable defective coloring, which relaxes the properness requirement, is also studied.[16](https://link.springer.com/rwe/10.1007/978-1-4614-6624-6_25-1)\n\n## Applications\n\n**Register allocation.** In compilation, program variables are vertices of an interference graph and simultaneously-live variables are joined by edges, so a minimum coloring gives a register assignment using a minimum number of registers; spilling is modeled by splitting a variable into two vertices linked by a preference edge whose penalty equals the copy cost.[18](https://www.gerad.ca/~alainh/G1384.pdf) Chaitin's formulation makes spill decisions from the register conflict graph with cost estimates of keeping a computation result in a register rather than in storage, producing better object code and much less compile time than the previous ad hoc techniques.[15](https://doi.org/10.1145/989393.989403)\n\n**Scheduling.** The survey literature names timetabling, train platforming, frequency assignment, and communication networks as application domains.[1](https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2009.00696.x)\n\n## Limitations and alternatives\n\nThe standard benchmark set comes from a DIMACS challenge in the fall of 1993, which also solicited results for related problems such as multi-coloring.[19](https://mat.tepper.cmu.edu/COLOR04/) On the 137 DIMACS graphs, a recent comparison reports the SAT-based ZykovColor solver solving 94 instances, versus 83 for gc-cdcl, 91 for POP-S, 92 for the assignment encoding, 91 for CliColCom, 63 for the exactcolors branch-and-price code, and 71 for [DSatur](https://www.edgepedia.org/dsatur); all SAT methods solve between 91 and 94.[6](https://arxiv.org/html/2504.04821) Published comparisons disagree on which exact approach is strongest: one reports that for DIMACS instances branch-and-price based on the ILP formulation gives the best performances[20](https://optimization-online.org/wp-content/uploads/2015/10/5159.pdf), while the newer instance counts place branch-and-price well behind the SAT-based solvers.[6](https://arxiv.org/html/2504.04821) Clique-based methods complement coloring solvers: a clique/coloring approach closed two open DIMACS instances (wap02a and wap08a) and improved one lower bound (r1000.1c)[21](https://www.andrew.cmu.edu/user/vanhoeve/papers/cliques_coloring_CP2022.pdf), and the chromatic number of r1000.1c was subsequently determined for the first time using exact decision diagrams in exact arithmetic.[22](https://bonndata.uni-bonn.de/catalog/datasets/10.60507/FK2/ZE9C3L/) Even so, graphs with as few as 125 vertices can remain unsolved optimally by the best exact algorithms.\n\nExact methods based on CP, SAT, and ILP generally do not scale beyond a few thousand vertices because the encodings become prohibitively large; in one experimental study the largest graph colored by a SAT encoding had around 14,000 vertices.[12](https://dl.acm.org/doi/fullHtml/10.1145/3603112) For massive dense graphs, GC-SLIM, a hybrid of tabu search with SAT-based local improvement, scales to dense graphs with several hundred thousand vertices and over 1.5 billion edges and beats state-of-the-art methods on large dense graphs.[12](https://dl.acm.org/doi/fullHtml/10.1145/3603112)\n\n## References\n\n1. [A survey on vertex coloring problems (Journal of Scheduling / Wiley)](https://onlinelibrary.wiley.com/doi/10.1111/j.1475-3995.2009.00696.x)\n2. [Vertex colouring (Combinatorics textbook chapter, University of Lethbridge)](https://www.cs.uleth.ca/~morris/Combinatorics/html/sect_colouring-Vertices.html)\n3. [A Survey of Graph Coloring - Its Types, Methods and Applications](https://reference-global.com/download/article/10.2478/v10209-011-0012-y.pdf)\n4. [NDMI012: Combinatorics and Graph Theory 2, Lecture 6 (Charles University)](https://iuuk.mff.cuni.cz/~ipenev/KG2S2022Lecture06.pdf)\n5. [Strengthened Partial-Ordering Based ILP Models for the Vertex Coloring Problem](https://ar5iv.labs.arxiv.org/html/2206.13678)\n6. [A Customized SAT-based Solver for Graph Coloring (ZykovColor)](https://arxiv.org/html/2504.04821)\n7. [Lecture 1: ILP Formulations for the Graph Coloring Problem (Univ. of Bonn)](https://www.or.uni-bonn.de/~held/hausdorff_school_22/slides/GraphColoringFormulations.pdf)\n8. [Richard M. Karp (1972). Reducibility among Combinatorial Problems. .](https://doi.org/10.1007/978-1-4684-2001-2_9)\n9. [Course notes on greedy graph coloring (Harvard, Salil Vadhan)](https://salil.seas.harvard.edu/file_url/439)\n10. [Chapter 13 Graph colouring algorithms (Husfeldt, survey chapter)](https://ar5iv.labs.arxiv.org/html/1505.05825)\n11. [Obtaining the Grundy chromatic number: How bad can my greedy heuristic coloring be? (Computers & OR, 2024)](https://www.sciencedirect.com/science/article/abs/pii/S0305054824001758)\n12. [SAT-boosted Tabu Search for Coloring Massive Graphs (GC-SLIM)](https://dl.acm.org/doi/fullHtml/10.1145/3603112)\n13. [Coloring With a Limited Paintbox (AMS Notices)](https://www.ams.org//journals/notices/202206/noti2490/noti2490.html)\n14. [Chapter 11. The Four-Colour Problem (Bondy & Murty notes)](https://faculty.etsu.edu/gardnerr/5340/notes-Bondy-Murty-GT/Bondy-Murty-GT-11-1.pdf)\n15. [Gregory Chaitin (2004). Register allocation and spilling via graph coloring. ACM SIGPLAN Notices.](https://doi.org/10.1145/989393.989403)\n16. [Equitable Coloring of Graphs (Springer reference-work chapter)](https://link.springer.com/rwe/10.1007/978-1-4614-6624-6_25-1)\n17. [Results and Problems on Equitable Coloring of Graphs](https://ar5iv.labs.arxiv.org/html/2504.14711)\n18. [Les Cahiers du GERAD: graph colouring models for scheduling with preferences](https://www.gerad.ca/~alainh/G1384.pdf)\n19. [Computational Series: Graph Coloring and its Generalizations (COLOR04)](https://mat.tepper.cmu.edu/COLOR04/)\n20. [An improved DSATUR-based Branch and Bound for the Vertex Coloring Problem](https://optimization-online.org/wp-content/uploads/2015/10/5159.pdf)\n21. [From Cliques to Colorings and Back Again (CP 2022)](https://www.andrew.cmu.edu/user/vanhoeve/papers/cliques_coloring_CP2022.pdf)\n22. [Chromatic Numbers from Exact Decision Diagrams in Exact Arithmetic](https://bonndata.uni-bonn.de/catalog/datasets/10.60507/FK2/ZE9C3L/)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Computational graph problems and algorithms › Graph coloring algorithms*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Sep 30, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/vertex-coloring", "markdown_url": "https://www.edgepedia.org/vertex-coloring.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Vertex coloring\", Edgepedia (EdgeChat), https://www.edgepedia.org/vertex-coloring. Edgepedia Community License 1.0.", "credit_md": "\"[Vertex coloring](https://www.edgepedia.org/vertex-coloring)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/vertex-coloring](https://www.edgepedia.org/vertex-coloring). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Vertex coloring\", Edgepedia (EdgeChat), https://www.edgepedia.org/vertex-coloring. Edgepedia Community License 1.0.", "speakable": "Vertex coloring is a graph algorithm assigning colors to vertices so adjacent vertices differ, minimizing colors used; it is NP-complete and models scheduling, register allocation, and frequency assignment." }