Everything about Graph coloring
Methodic assignment of colors to elements of a graph
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face so that no two faces that share a boundary have the same color. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Graph coloringA 5-minute orientation
- Skim a recent paper: Graph coloring with physics-inspired graph neural networksInfluential work since 2022
- Pick up a classic book: Chromatic graph theoryThe most-reprinted book on the subject
- Read the landmark paper: A Parallel Graph Coloring HeuristicCited 162 times
- Go sideways: Edge coloringA closely related topic
- Go sideways: Chromatic polynomialA closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
A Parallel Graph Coloring Heuristic
Signed graph coloring
Graph Coloring Using Eigenvalue Decomposition
Oriented graph coloring
Randomized online graph coloring
Coloring graph products — A survey
New Graph Coloring Algorithms
σ-polynomials and graph coloring
🆕 Influential since 2022
Graph coloring with physics-inspired graph neural networks
Graph matching for knowledge graph alignment using edge-coloring propagation
Qudit-inspired optimization for graph coloring
Efficient and Robust Graph Coloring Algorithm for Graph Coloring Problem: Malatya Vertex Coloring Algorithm
Applications of graph coloring in various fields
📚 Books worth reading
Chromatic graph theoryGary Chartrand, Zhang, Ping · 2008
Graph coloring problemsTommy R. Jensen · 1995
Combinatorial NullstellensatzXuding Zhu, R. Balakrishnan · 2021- 📕Topics in Chromatic Graph TheoryLowell W. Beineke, Robin J. Wilson · 2015
Introduction to graph theoryDouglas Brent West · 1996
Edge-colourings of graphsStanley Fiorini · 1977
Graph colouring and variationsD. de Werra, A. Hertz · 1989- 📕A Sharp threshold for random graphs with a monochromatic triangle in every edge coloringEhud Friedgut · 2006
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Edge coloring In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color…
- Chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a…
- Vizing's theorem In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than…
- Total coloring Unsolved problem in mathematics Conjecture: χ″(G)≤Δ(G)+2. More unsolved problems in mathematics In graph theory, total coloring is a type of graph coloring…
- Equitable coloring In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that No…
- List coloring In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It…
- Chvátal graph In the mathematical field of graph theory, the Chvátal graph is an undirected graph with 12 vertices and 24 edges, discovered by Václav Chvátal in 1970…
- Nowhere-zero flow In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs…