Balanced complete multipartite blow-up Created 2026-10-05 Updated 2026-10-07
The balanced complete multipartite blow-up replaces each vertex of the complete graph by an independent set of vertices, placing every possible edge between different sets and none inside a set. Every fixed graph of chromatic number at most embeds into for sufficiently large .
Chromatic index 2026-10-14
The chromatic index , also called the edge chromatic number, is the least number of labels in a proper edge colouring of a finite undirected graph without self-loops. Equivalently, it is the smallest number of matchings in a graph whose set partition covers all the edges. We take when there are no edges. For an arbitrary edge colouring, one colour always suffices whenever an edge exists, so properness is essential to this definition. The chromatic number instead colours vertices.[ref]
To establish an exact chromatic index, supply both a proper edge colouring and a reason that fewer colours cannot work. Every edge at a fixed vertex must have its own colour, giving the lower bound , where is the maximum degree of a graph. The bound need not be attained: it counts a single resource's workload, while conflicts can also accumulate around a graph cycle.
Figure 1.
Worked proper edge colourings: a triangle in a graph needs three colours, while an even cycle graph needs two
. Numbers beside edges are colour labels; letters at dots are vertices. Both graphs have maximum degree of a graph two. The triangle in a graph has three pairwise conflicting edges, while opposite edges of the square can share a colour. Details.
For the triangle in a graph with edges , every pair of edges shares a vertex, so all three require different labels. The assignment works, proving although . In its line graph, those three edges become a three-vertex clique. Treating this as three pair-resource jobs makes the obstruction tangible: each resource has only two jobs, but every pair of jobs conflicts, so no slot can contain two jobs.
For the square cycle graph with edges , use and . Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since , this proves . More generally, alternation closes on any even cycle graph , . On an odd cycle , , two-colour alternation would make the last and first edges share a colour at their common vertex; a third colour on the last edge suffices. Thus even cycle graphs have chromatic index two and odd cycle graphs have chromatic index three. These exact examples show why maximum degree of a graph alone does not determine the answer.
Chromatic number Created 2026-09-24 Updated 2026-10-14
For a nonempty finite simple graph , the chromatic number is the least positive integer for which has a proper vertex graph coloring with at most colours. To establish an exact chromatic number, give a colouring using that many colours and explain why fewer cannot suffice. A colouring alone gives only an upper bound.[ref]
Figure 1.
Optimal graph colorings of the cycle graphs
. Numbers inside dots are colour labels, and labels outside are vertices. The cycle graph alternates two colours. The odd cycles need three, although is a triangle-free graph. Details.
These small graphs show why the chromatic number measures more than the presence of triangles in a graph:
For a cycle graph of even length, alternating two colours closes consistently; for an odd cycle, it does not, and a third colour on the final vertex suffices. More generally, the two-colourability criterion for bipartite graphs says that exactly when is a bipartite graph, and the odd-cycle characterization of bipartite graphs identifies the obstruction as an odd cycle. A nonempty graph with no edges has chromatic number one; a bipartite graph with at least one edge has chromatic number exactly two.
In the pairwise-conflict scheduling model of graph coloring, is the least number of interchangeable slots needed. This turns a drawing into an optimization question: how many groups of compatible activities are unavoidable? Greedy coloring constructs a valid grouping quickly, but its number of colours can exceed the chromatic number.
For a finite graph, let count the vertices on a longest directed path in an acyclic orientation . Its minimum over those orientations is the chromatic number. A proper -colouring gives an orientation from smaller to larger colours, so every directed path has strictly increasing colours and at most vertices. Conversely, assign to each vertex the number of vertices in a longest directed path ending there. Along an edge this number increases: an ending path at cannot contain without forming a directed cycle, so it can be extended. The resulting labels give a proper colouring using at most colours. These two constructions prove equality. Counting edges instead of vertices in path length subtracts one from the displayed minimum.
Chromatic polynomial Created 2026-09-24 Updated 2026-10-14
The chromatic polynomial turns a graph coloring problem into a counting problem: how many choices remain when adjacent vertices must have different colours? For a finite simple graph and a positive integer , is the number of proper vertex colorings using a fixed, distinguished palette of colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.
Consider the three-vertex path graph ----. Choose in ways, then in ways, then in ways: and may agree because they are not adjacent. The multiplication principle gives
Adding the edge makes the three-vertex complete graph . Now must avoid both preceding colours, so
With three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are and : the extra constraint makes the triangle impossible to colour.
Figure 1.
All twelve proper colourings of a three-vertex path using a three-colour palette
. Details.
For a nonempty graph, the chromatic number records only the first positive integer for which . The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is , and for the triangle it is . Counting assignments also gives a useful interpretation for scheduling: if adjacent vertices represent tasks that must use different slots, the chromatic polynomial counts the valid assignments to named slots. Adding a conflict edge can only remove assignments.
The chromatic polynomial also remembers some of the graph's structure. For a simple graph with vertices and edges, its leading terms are ; its degree of a polynomial gives the number of vertices, and its next coefficient gives the number of edges. It does not determine the graph completely. A four-vertex path graph and a four-vertex star graph are not related by a graph isomorphism, but both are trees and have chromatic polynomial .
The early connection to map colouring appears in George D. Birkhoff's article [ref]. For a derivation of the counting recurrence and its leading coefficients, see Paul Johnson's MAS 341 lecture on chromatic polynomials.
Chromatic polynomial determines a Turán graph Created 2026-10-14 Updated 2026-11-05
For integers , if a simple graph has the same chromatic polynomial as the Turán graph , it has the same number of vertices and edges, and the same chromatic number . It is therefore -free and attains equality in Turán's theorem. The equality case forces it to be isomorphic to .
Claude Berge Created 2026-10-14 Updated 2026-11-05
Claude Berge was a mathematician whose work helped establish modern graph theory, with connections to combinatorics, game theory and optimization. His books gave common mathematical language to networks arising in different applications. He also formulated the strong perfect graph conjecture, a major stimulus to research on perfect graphs.[ref] A perfect graph has equal chromatic number and clique number in every induced subgraph. The condition expresses when the obvious lower bound for graph coloring, supplied by mutually adjacent vertices, is always attainable; requiring it in every induced subgraph is essential.
Figure 1.
Portrait of Claude Berge
. Mihály Hujter (HUJTER Mihály), photograph in New York, 1985; Commons records VRT permission ticket 2025052210006236. Creative Commons Attribution-Share Alike 4.0 International., via Wikimedia Commons. Source.
Clique number Created 2026-10-06 Updated 2026-10-14
The clique number is the maximum number of vertices in a clique of a finite graph:
We use for the graph with no vertices. For a nonempty complete graph, ; for the five-vertex example, .
If the graph contains and no as subgraphs, its clique number is exactly , because every larger clique contains a clique with vertices. Also : a proper vertex coloring must assign different colors to all members of any clique. This lower bound need not be an equality; the cycle graph has clique number and chromatic number .
Colour-critical vertex Created 2026-10-06 Updated 2026-10-14
A vertex is colour-critical if deleting it lowers the chromatic number by one. If and , an embedding of into a complete -partite graph inside one neighbourhood extends to an embedding of . This supplies maximum-degree obstructions in extremal graph theory.
Complete graph Created 2026-09-24 Updated 2026-10-14
A complete graph is a simple graph in which every two distinct vertices are joined by an edge. The finite complete graph on vertices is denoted . Here the edges are undirected, and self-loops are excluded. The usual pictures below use : is a single vertex, a single edge, and a triangle in a graph.[ref]
Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same graph through a graph isomorphism. Crossing lines away from the drawn vertices do not add new vertices or edges.
Figure 1.
Complete graphs with one through five vertices
. Each original drawing joins every pair of distinct vertices exactly once. The complete graphs have respectively edges. Intersections of drawn lines in the panel are not additional vertices. Details.
There are unordered pairs of distinct vertices, so this is the edge count of a complete graph. Each vertex has vertex degree . The degree-sum formula gives the same count: . These formulas make a complete graph the upper extreme for edge counts among simple graphs of a fixed size.
This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten vertices require edges, while twenty require . Adding one more vertex to introduces further edges. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.
A proper vertex coloring of must give every vertex a different color, so its chromatic number is . For , its independence number is : two distinct vertices already have an edge between them. Thus complete graphs provide immediate test cases for graph coloring and independent sets.
Crown graph Created 2026-10-14 Updated 2026-10-20
A crown graph is a complete bipartite graph with a perfect matching removed. For it has chromatic number two, but greedy coloring in the order uses colors: the matched pair gets the same new color, and every subsequent pair sees all earlier colors.
Four color theorem 2026-10-14
Every finite planar graph has chromatic number at most four. This stronger theorem is distinct from the elementary five colour theorem; the latter's Kempe chain proof does not prove this assertion.
Graph coloring Created 2026-10-14 Updated 2026-10-20
A graph coloring assigns labels called colours to elements of a graph, subject to specified constraints. Here we focus on proper vertex colouring of a simple graph : it is an undirected graph with a finite set of vertices, and a colouring with at most colours is a function
The colour labels need not be visual colours: they can represent time slots or resources. Unused labels are allowed. Properness concerns graph adjacency, so moving vertices in a drawing does not change whether the graph coloring is valid.[ref]
Each colour class is an independent set: no edge has both endpoints in it. Conversely, a set partition of into independent sets gives a proper graph coloring by assigning one colour to each part. Thus graph coloring groups mutually compatible objects, and its chromatic number asks for the fewest such groups.
For an illustrative scheduling model, let each vertex represent an activity of equal duration and each edge represent a pair that cannot occur in the same time slot. A proper graph coloring is then a schedule respecting those pairwise conflicts. If the conflicts form a cycle graph with edges , activities can share one slot and another. This model assumes interchangeable slots and includes only the pairwise conflicts encoded by the graph.[ref]
The word "colouring" also occurs in edge coloring, which requires different colours on edges sharing an endpoint. The chromatic number discussed here always refers to proper vertex colouring.
Graph minor Created 2026-10-05 Updated 2026-10-14
A graph minor compresses connected regions of a graph into single vertices while retaining selected connections between them. For finite simple graphs, means that some sequence of deleting vertices, deleting edges, and performing edge contractions produces up to graph isomorphism. Deleting a vertex also deletes all its incident edges; deleting an edge leaves its endpoints. The edge contraction convention here removes resulting self-loops and duplicate edges.[ref]
For an exact small example, let be the cycle graph with vertices and edges . Contract to a new vertex . The surviving edges are , giving the complete graph . Thus , although has no triangle in a graph as a subgraph. The branch sets of a graph minor are , with the original edges witnessing all three required adjacencies. The first panel of the edge contraction diagram shows this operation.
A subgraph uses existing vertices and edges; a topological minor permits a graph subdivision of the target as a subgraph, so target edges become graph paths with mutually disjoint interiors and no target vertex in an interior. An ordinary graph minor permits whole connected branch sets of a graph minor in place of target vertices. Every topological minor is a graph minor, by contracting the replacement graph paths.[ref]
The converse fails. Take the tree with edges . Contracting gives the star graph . Yet the original tree has maximum degree three, whereas every graph subdivision of retains a centre of degree of a vertex four. Hence is a graph minor but not a topological minor of this tree. The difference is that a connected branch set of a graph minor may gather connections incident to several original vertices.
The counts of vertices and edges never increase under these operations. However, the example shows that being a bipartite graph is not preserved: its graph minor contains an odd cycle. Its chromatic number also increases from two to three. A connected graph stays connected under an edge contraction, because the image of each graph path still connects its endpoints, but deletion can disconnect it. Thus one must check the particular graph property before treating it as preserved by taking graph minors.
Being a planar graph is preserved: in a crossing-free drawing, shrink a contracted edge and bring its incident edges into the merged vertex; deletion merely removes parts of the drawing. This makes a nonplanar graph minor a certificate that the original graph is nonplanar. More strongly, for a finite simple graph, being a planar graph is equivalent to having neither the complete graph nor the complete bipartite graph as a graph minor. Finding the corresponding branch sets of a graph minor settles nonplanarity even when no literal or subgraph is present. The converse is a substantial theorem, rather than a consequence of preservation alone.[ref]
Greedy coloring 2026-10-14
For a finite simple graph, choose an order of its vertices and process them one at a time. Give each vertex the smallest positive colour label not already used by its coloured neighbours, and keep all earlier assignments. This is greedy coloring: each step makes a locally available choice. The resulting graph coloring is proper because, for each edge, its later endpoint avoids the colour of its earlier endpoint.[ref]
If the maximum degree of a graph is , a vertex has at most previously coloured neighbours, forbidding at most that many distinct colours. At least one label among remains available. Consequently every order gives
This is an upper bound, not a promise that greedy coloring attains the chromatic number.[ref]
Figure 1.
Two orders for greedy coloring of the same path graph
. The edges are in both drawings. Each dot shows its assigned colour number, with the vertex label above and its processing step below. The order uses two colours; the order uses three. Details.
Consider the path graph with edges . In the order , greedy coloring assigns the colours respectively. In the order , it assigns colours in processing order: vertices both get colour , then vertex gets colour , and finally vertex sees colours and at its two neighbours and must take colour . Written in vertex order , this second colouring is .
The path graph has chromatic number two: the first assignment achieves two colours, and any edge rules out one. Its maximum degree of a graph is two, so three colours in the second assignment still satisfy the bound. The extra colour comes entirely from the processing order. The crown graph gives a larger family where a poor order can make greedy coloring use arbitrarily many colours although the chromatic number remains two.
Grötzsch graph Created 2026-10-14 Updated 2026-11-05
The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges , with indices interpreted modulo five; add and for every . There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.
Give colours , give each the colour of , and give colour 4. This is a proper vertex colouring. The Mycielskian chromatic increase proves that three colours are impossible, so the chromatic number is exactly four. The Mycielskian triangle preservation proves that this is a triangle-free graph. In particular its clique number is only two, even though its chromatic number is four.
Figure 1.
From a three-colour cycle graph to the four-colour Grötzsch graph
. The outer pentagon on the right retains the original vertices; the inner ring contains Mycielski shadow vertices and has no ring edges. The central Mycielski apex receives colour 4. Numbers identify colours independently of the fills, and labels identify the vertices. Crossings without dots are not vertices. Details.
The Mycielski apex has an independent set as its graph neighbourhood, yet all three old colours are needed there in any three-colour proper vertex colouring of the subgraph obtained by deleting it. Thus a locally easy group of mutually nonadjacent neighbours can carry globally incompatible colour requirements. Absence of triangles in a graph alone cannot bound the chromatic number.
Independence number Created 2026-10-03 Updated 2026-10-14
The independence number is the largest cardinality of an independent set in a finite simple graph:
It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.[ref]
For the cycle graph , the independent set shows that . Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus . There are five largest independent sets, obtained by rotating around the cycle graph, and five corresponding minimum vertex covers.
For the complete bipartite graph , an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so . A triangle in a graph has independence number one. A graph with no edges and vertices has independence number , including when .
The complement correspondence between vertex covers and independent sets gives, with ,
Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph ; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.
For a nonempty graph, every colour class of a proper vertex colouring contains at most vertices. Counting all the vertices therefore gives
Since the chromatic number is an integer, the bound rounds up: for the cycle graph , . It is attained by assigning colour to , colour to , and colour to . All five edges, including , have differently coloured endpoints.
Lovász number Created 2026-10-05 Updated 2026-10-14
The Lovász number of a finite simple graph is the semidefinite program value
where is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.
Lovász theorem on Kneser graphs Created 2026-10-06 Updated 2026-10-14
For integers , the chromatic number of the Kneser graph is . The upper bound colours by the least element among the first elements, with one final colour for all other sets. The Gale hemisphere lemma and the Lusternik-Schnirelmann-Borsuk theorem give the matching lower bound.