Graph coloring

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 $G=(V,E)$: it is an undirected graph with a finite set of vertices, and a colouring with at most $k$ colours is a functionThe 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 $c^{-1}(i)$ is an independent set: no edge has both endpoints in it. Conversely, a set partition of $V$ 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 $C_4$ with edges $12,23,34,41$, activities $1,3$ can share one slot and $2,4$ 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.

A face colouring of a plane graph assigns colours to its faces of a plane graph so that distinct faces sharing an edge have different colours. Equivalently it is a graph colouring of the dual graph, disregarding dual loops that arise when an original bridge is incident to only one face on both sides. Isolated contact at a vertex does not impose a colour constraint.

For the dual graph of a plane tree, the face-adjacency graph is the original tree, because taking the geometric dual twice recovers the original embedding on the sphere. Every nontrivial tree is a bipartite graph, so its dual requires exactly two face colours, even though that dual has only one vertex and all its edges are loops. A graph drawing must retain the nesting of those loops to preserve the correct face-adjacency graph.

A graph coloring with two available colors in which adjacent vertices receive different colors. A graph admits a two-coloring exactly when it is a bipartite graph. Every nonempty connected bipartite graph has two such colorings when the two color names are distinguished.

A proper vertex coloring assigns labels to the vertices of a graph so that vertices joined by an edge have different labels. Each colour class is an independent set. The chromatic number is the least number of labels needed for this form of graph coloring.

Maintain lists of available colours, tentatively colour small random portions, erase conflicts and prune colours used by neighbours. In a triangle-free graph, a vertex's neighbours form an independent set, which enables local estimates. Track list size and average remaining neighbour congestion per colour; prune unusually congested colours before the next round. Concentration and the Lovász local lemma preserve these invariants until lists have enough slack for completion. Tracking averages matters because triangle-free graphs can still contain many four-cycles and need not have uniform per-colour congestion.

If each neighbourhood misses a fixed positive fraction of the possible pairs at a large degree bound, randomly assign about half that many colours and erase vertices with monochromatic incident edges. A nonadjacent neighbour pair can share a retained colour, giving a neighbour-colour saving. Write the number of successful repeated colours as a difference of two certifiable functions: colours with a nonadjacent pair, minus those for which a neighbour loses that colour. Both change by at most two under one-coordinate changes and have constant-size certificates. Talagrand's convex distance inequality and the Lovász local lemma make their linear expected saving simultaneous at all high-degree vertices; low-degree vertices have slack already. This yields a colouring using a fixed positive fraction fewer than the degree bound.

For a uniformly chosen vertex $Z$, minimize the information entropy of its color over proper colorings. Multiply by the number of vertices to define this weight. Minimizing the color entropy gives the strongest contribution from that graph in the entropy weight of a graph cover inequality.

If graphs $G_i$ cover the edges of an $n$-vertex graph with independence number at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an independent set, leaving conditional entropy at most ${\log }_2\alpha$. The mutual information carried by the colors is at most $n^{-1}{\sum }_{i}w(G_i)$, proving the bound.

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 $\Delta (G)$, a vertex has at most $\Delta (G)$ previously coloured neighbours, forbidding at most that many distinct colours. At least one label among $1,\dots ,\Delta (G)+1$ remains available. Consequently every order givesThis is an upper bound, not a promise that greedy coloring attains the chromatic number.^[ref]

Consider the path graph $P_4$ with edges $12,23,34$. In the order $1,2,3,4$, greedy coloring assigns the colours $1,2,1,2$ respectively. In the order $1,4,2,3$, it assigns colours $1,1,2,3$ in processing order: vertices $1,4$ both get colour $1$, then vertex $2$ gets colour $2$, and finally vertex $3$ sees colours $2$ and $1$ at its two neighbours and must take colour $3$. Written in vertex order $1,2,3,4$, this second colouring is $1,2,3,1$.

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.

Let $x$ have two nonadjacent neighbours $y,z$ in a finite graph $G$, with $G-\{y,z\}$ connected. Then $\chi (G)\le \Delta (G)$. Give $y,z$ one common colour. In a spanning tree of the remaining graph rooted at $x$, order vertices from larger to smaller distance from the root and colour greedily in that order. Every vertex before $x$ has an uncoloured parent, so at most $\Delta (G)-1$ colours are forbidden there. At $x$, the two initial neighbours use the same colour, so again at most $\Delta (G)-1$ distinct colours are forbidden. This constructs a proper colouring from a palette of $\Delta (G)$ colours. It is a useful local step in Brooks' theorem.

In a proper partial graph coloring, let $R_v$ count coloured neighbours and $D_v$ count their distinct colours. The saving $S_v=R_v-D_v$ leaves $K-D_v$ available colours for only $d(v)-R_v$ initially uncoloured neighbours. If the displayed inequality holds at every vertex, ordinary greedy completion succeeds. Each additionally coloured neighbour removes at most one available colour while also reducing the number of uncoloured neighbours by one.

The number of coloured neighbours of $v$ minus the number of distinct colours on those neighbours. Repeated colours among pairwise nonadjacent neighbours reduce the number of unavailable colours without increasing the number of neighbours still to colour.

This decision problem asks whether a finite undirected graph has a graph colouring with three colours. It is NP-complete: a colouring certifies membership in NP, while 3-SAT reduces using Boolean-pair colouring gadgets and three-colour clause gadgets.

Take auxiliary graph triangles $a,b,c$ and $d,t,e$, join $a$ to $d$, and add edges $bx,cy,ez$. When $t$ has colour $T$ and the inputs $x,y,z$ have colours in $\{T,F\}$, this graph admits an extension to a graph colouring with three colours exactly when at least one input is $T$. All-false inputs force $a=d=F$, contradicting their edge. Conversely, use $(a,b,c,d,e)=(T,F,B,F,B)$ if $x=T$, $(T,B,F,F,B)$ if $x=F,y=T$, and $(F,T,B,B,F)$ if $x=y=F,z=T$. The extension property is necessary for both directions of a polynomial-time many-one reduction.

Two graph triangles sharing a vertex $B$ force their two opposite edges to use the same two colours in a graph colouring with three colours. A palette graph triangle $T,F,B$ and another graph triangle $u,\bar{u},B$ therefore force the literal pair to have opposite Boolean colours. This gadget is used in a reduction from 3-SAT to the three-colourability problem.

If every vertex subset of size at least $m$ contains an independent set of size $r$, repeatedly colour and remove an $r$-element independent set while at least $m$ vertices remain. Giving each remaining vertex its own colour uses at most $|V|/r+m$ colours.

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

Assign a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct vertices are nonadjacent. A handle is a further unit vector $h$. In the handle formulation of the Lovász number, one minimizes ${\max }_v|h\cdot u_v{|}^{-2}$ over representations and handles. Orthonormal here does not mean every pair of assigned vectors is orthogonal.

Tensor products of the assigned vectors represent strong graph powers, and tensor products of the handle have squared inner products equal to products of the original ones. The vectors assigned to an independent set are orthonormal. Bessel inequality then bounds its size by the largest inverse squared handle inner product. Taking roots and minimizing proves $c(G)\le \vartheta (G)$.

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.

A vector $k$-coloring, for $k>1$, assigns a unit vector $v_i$ to each vertex of a graph, such that $⟨v_i,v_j⟩\le -1/(k-1)$ on every edge. A graph colouring with $k$ colors gives a vector $k$-coloring by placing the colors at the vertices of a regular simplex. The Gram matrix of these vectors allows semidefinite programming to search for such a representation.

A strict vector $k$-coloring requires equality $⟨v_i,v_j⟩=-1/(k-1)$ on every edge. The least admissible $k$ is the complement theta number for a graph with an edge. Allowing merely an inequality defines the potentially smaller vector chromatic number.

For unit vectors $u,v$ and a random normal $a$ with independent standard normal distribution coordinates,The Gaussian distribution is invariant under orthogonal transformations. Projecting onto the plane spanned by $u,v$ therefore gives a uniformly distributed direction. If the angle between $u,v$ is $\theta$, the sign-disagreement directions form two sectors of total angle $2\theta$ out of $2\pi$. The endpoint cases $u=v$ and $u=-v$ give probabilities zero and one directly.

A $k$-semicoloring of a finite graph assigns one of $k$ colors to every vertex and is a proper graph colouring on an induced subgraph containing at least half the vertices. This is weaker than a proper coloring of the whole graph, and is useful as an intermediate step in a randomized algorithm.

Suppose a graph with $n$ vertices and $m>0$ edges has a vector coloring with adjacent inner products at most $-1/2$. Take $r$ independent copies of random hyperplane rounding and use the $r$ signs as a color. Each edge remains monochromatic with probability at most $3^{-r}$, so the expected number $B$ of monochromatic edges is at most $m{3}^{-r}$ by linearity of expectation.

Choose $r=\max \{0,\lceil {\log }_3(4m/n)\rceil \}$. Then Markov inequality gives $\mathbb{P}(B>n/2)\le 1/2$. On success, delete one endpoint of every monochromatic edge. This random alteration method leaves at least $n/2$ vertices properly colored withThe removed vertices can retain their original colors, as the semicoloring only requires the retained induced subgraph to be proper. A failed draw can be detected and repeated, with at most two trials on average. The case $m=0$ needs just one color. This is the elementary independent-hyperplane construction in Karger, Motwani and Sudan's paper on approximate graph coloring.

An edge colouring assigns a label called a colour to every edge of a graph: it is a function $c:E(G)\to \{1,\dots ,k\}$. Here this definition allows arbitrary assignments. Two edges sharing a vertex may receive the same colour. A proper edge colouring imposes the additional condition that such edges receive different colours. Some textbooks use "edge colouring" as shorthand for this proper version; check the convention before applying a theorem.^[ref]

The distinction matters in Ramsey theory. In a red-blue edge colouring of a complete graph, a triangle in a graph is monochromatic when its three edges have the same colour. These are arbitrary edge colourings: forbidding equal colours on edges sharing a vertex would forbid the very monochromatic triangles in a graph being sought. For example, assigning red to every edge of $K_3$ is a valid arbitrary edge colouring, although it is not a proper edge colouring. Colour labels can also stand for time slots: then proper edge colouring turns incompatible jobs into separate rounds.

A proper edge colouring gives different labels to any two distinct edges sharing a vertex. We work with finite undirected graphs without self-loops; distinct parallel edges in a multigraph must also have different colours. For a simple graph, whose edges are two-element sets, the condition isEvery colour class $M_i=\{e\in E(G):c(e)=i\}$ is a matching in a graph. Conversely, a set partition of the edges into matchings in a graph supplies a proper edge colouring. Thus minimizing colours means grouping all the edges into as few matchings in a graph as possible.

The line graph makes the relationship with proper vertex colouring explicit: replace each original edge by a vertex, joining two new vertices exactly when their original edges share an endpoint. A proper edge colouring of $G$ becomes a proper vertex colouring of its line graph $L(G)$, so $\chi \prime (G)=\chi (L(G))$. For a multigraph, retain a distinct new vertex for each parallel edge.^[ref]

Suppose each job occupies two distinct resources for one whole slot, and each resource can serve at most one job in that slot. Make resources vertices and jobs edges. Two jobs conflict exactly when their edges share a vertex, so a valid schedule is a proper edge colouring. Each slot is a matching in a graph; the chromatic index is the minimum number of slots. The colour labels specify the slots, rather than physical colours. This model assumes all jobs are available initially, with equal duration, interchangeable slots and no additional conflicts. The school-timetable motivation in Graph Theory by Reinhard Diestel (author-hosted Colouring preview, opening paragraphs, pp. 123–124) uses this resource-pair interpretation.

Here is a complete example. Two technicians $A,B$ must each use three instruments $X,Y,Z$ once. Each job needs its technician and its instrument simultaneously. The six jobs are the edges of the complete bipartite graph $K_{2,3}$:Within each $M_i$, the two jobs use different technicians and different instruments, so $M_i$ is a matching in a graph. The three matchings in a graph together cover every job exactly once. Technician $A$ has three jobs, so fewer than three slots cannot suffice; the displayed schedule uses three. This is an optimal proper edge colouring with chromatic index three, witnessed by both a schedule and a resource-workload lower bound.

Repeated jobs requiring the same resource pair become distinct parallel edges of a multigraph, rather than one edge. Additional restrictions change the problem: prescribed allowed slots lead to list edge coloring, while unequal durations, deadlines, or jobs needing more than two resources require a richer scheduling model. Selecting a largest matching in a graph solves a single-round question; a shortest complete schedule must organize all jobs across rounds.

Each edge has a list of allowed colors; a list edge coloring chooses an allowed color on each edge, giving different colors to incident edges. The list-chromatic index is the uniform list-size threshold guaranteeing success.

The list-chromatic index is the least integer $q$ such that every assignment of at least $q$ allowed colors to each edge admits a list edge coloring. Uniform identical lists show it is at least the chromatic index. The Galvin theorem for bipartite list edge coloring gives equality for bipartite graphs.

A bipartite graph has equal list-chromatic index, chromatic index and maximum degree of a graph $\Delta$. Start with a proper $\Delta$-edge coloring. Orient its line graph toward smaller colors at one part and toward larger colors at the other. An edge of color $c$ has at most $(c-1)+(\Delta -c)=\Delta -1$ outgoing neighbours. Every induced orientation has a digraph kernel obtained from a stable matching in a bipartite graph with those preferences. Apply the kernel list-coloring lemma.

The chromatic index $\chi \prime (G)$, 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 $\chi \prime (G)=0$ 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 $\chi (G)$ 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 $\chi \prime (G)\ge \Delta (G)$, where $\Delta (G)$ 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.

For the triangle in a graph $K_3$ with edges $ab,bc,ca$, every pair of edges shares a vertex, so all three require different labels. The assignment $c(ab)=1,c(bc)=2,c(ca)=3$ works, proving $\chi \prime (K_3)=3$ although $\Delta (K_3)=2$. 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 $C_4$ with edges $ab,bc,cd,da$, use $c(ab)=c(cd)=1$ and $c(bc)=c(da)=2$. Each colour class is a matching in a graph, and each vertex has one edge of each colour. Since $\Delta (C_4)=2$, this proves $\chi \prime (C_4)=2$. More generally, alternation closes on any even cycle graph $C_{2m}$, $m\ge 2$. On an odd cycle $C_{2m+1}$, $m\ge 1$, 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.

For every finite simple graph, Vizing's theorem givesHere $\Delta (G)$ is the maximum degree of a graph, taken as zero when there are no vertices. A bipartite graph has the stronger equality $\chi \prime (G)=\Delta (G)$. The six-job complete bipartite graph above attains this lower bound, while the triangle in a graph attains the extra-colour alternative. The simple-graph restriction in the upper bound matters.^[ref]

The bipartite graph equality still holds for finite loopless multigraphs, with parallel edges counted separately in each vertex degree. For instance, $r$ parallel jobs between two resources need exactly $r$ slots: every pair conflicts, and $\Delta =\chi \prime =r$. For a general finite loopless multigraph, however, the simple graph upper bound can fail. Put two parallel edges on each side of a triangle in a graph. All six edges pairwise share a vertex, so each needs its own colour; every vertex has degree of a vertex four. Consequently $\chi \prime =6>\Delta +1=5$. A multiplicity-aware bound is $\chi \prime (G)\le \Delta (G)+\mu (G)$, where $\mu (G)$ is the largest number of parallel edges between a pair of vertices. The doubled triangle in a graph has $\mu =2$ and attains that bound. These statements exclude self-loops; the two-distinct-resource scheduling model excludes them too.^[ref]

For historical orientation, Graph Theory by Reinhard Diestel (Colouring preview, §5.3, p. 132) dates the bipartite equality to 1916 and Vizing's theorem to 1964. These are textbook attributions; the original papers have not been inspected here. The results state existence of optimal or nearly optimal proper edge colourings, rather than saying that arbitrary greedy choices will find them. The list-chromatic index asks the further question of success for every sufficiently large family of allowed-colour lists.

A proper three-color edge coloring of a cubic graph. Label its colors by the nonzero elements of ${\mathbb{F}}_2^2$: the incident colors at each vertex then sum to zero. On a planar map without bridges in a graph, integrating these labels on the dual graph gives a four-color face coloring. On a torus, a nonzero period can obstruct this integration.

For a nonempty finite simple graph $G$, the chromatic number $\chi (G)$ is the least positive integer $k$ for which $G$ has a proper vertex graph coloring with at most $k$ 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]

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 $\chi (G)\le 2$ exactly when $G$ 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, $\chi (G)$ 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.

This is the least number of colors needed to color all points of Euclidean space so that points at Euclidean distance one receive different colors. Any finite unit-distance graph embedded in the space gives a lower bound. If $p$ is prime, the characteristic vectors of all $(2p-1)$-subsets of $[4p-1]$, divided by $\sqrt{2p}$, give such a graph: its edges are exactly pairs intersecting in $p-1$ points. The prime-power modular intersection bound bounds an independent set by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$, and hence gives $\chi ({\mathbb{R}}^{4p-1})\ge \left(\genfrac{}{}{0ex}{}{4p-1}{2p-1}\right)/\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

A vertex $v$ is colour-critical if deleting it lowers the chromatic number by one. If $\chi (F)=r+1$ and $\chi (F-v)=r$, an embedding of $F-v$ into a complete $r$-partite graph inside one neighbourhood extends to an embedding of $F$. This supplies maximum-degree obstructions in extremal graph theory.

The Mycielski construction replaces a graph $G$ with a graph $\mu (G)$ having one shadow vertex for each original vertex and one further vertex adjacent to every shadow. It satisfiesand preserves triangle-freeness. Iterating it from the five-cycle gives triangle-free graphs of arbitrarily large chromatic number.

Here $G$ is a finite simple graph with at least one vertex; it need not have an edge. The Mycielskian separates two ways of needing many colours: a large clique forces distinct colours immediately, but a triangle-free graph can impose incompatible choices through its whole pattern of graph adjacency. The Mycielski construction increases that global constraint while preserving the absence of triangles in a graph.

Write the vertex set of $G$ as $\{v_1,\dots ,v_n\}$, with $n\ge 1$. Keep these vertices, add distinct Mycielski shadow vertices $u_1,\dots ,u_n$, and add a Mycielski apex $w$. The vertex set and complete list of edges areThere are no other edges: the Mycielski shadow vertices form an independent set, $w$ has no original vertex as a neighbour, and $u_i$ is not adjacent to $v_i$. Each Mycielski shadow vertex copies its original vertex's graph neighbourhood within the original vertex set, not its position in the drawing. This is the construction in the inspected research paper.^[ref]

For $n$ original vertices and $m$ original edges, direct counting gives $2n+1$ vertices and $3m+n$ edges. The original vertices induce a copy of $G$, so no original graph adjacency is lost. A drawing crossing is not an extra vertex.

Start with the complete graph $K_2$, whose only edge is $v_1{v}_2$, abbreviating $\{v_1,v_2\}$. Its Mycielskian has exactly the edges $v_1{v}_2,u_1{v}_2,u_2{v}_1,w{u}_1,w{u}_2$. Reading them as $v_1,v_2,u_1,w,u_2,v_1$ gives the cycle graph $C_5$. A proper vertex colouring gives $v_1,u_1$ colour 1, $v_2,u_2$ colour 2, and $w$ colour 3. Two colours cannot close an odd cycle, so its chromatic number is exactly three.

The Grötzsch graph is the Mycielskian of the five-vertex cycle graph. Take original edges $v_i{v}_{i+1}$, with indices interpreted modulo five; add $u_i{v}_{i-1},u_i{v}_{i+1}$ and $w{u}_i$ for every $i$. There are eleven vertices and twenty edges: five original, ten between originals and Mycielski shadow vertices, and five from the Mycielski apex.

Give $v_1,\dots ,v_5$ colours $(1,2,1,2,3)$, give each $u_i$ the colour of $v_i$, and give $w$ 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.

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.

A Mycielski shadow vertex $u_i$ has graph neighbourhood $N_G(v_i)\cup \{w\}$ in $\mu (G)$. Its neighbours other than the Mycielski apex are original vertices. All Mycielski shadow vertices form an independent set.

The Mycielski apex is the added vertex adjacent to every Mycielski shadow vertex and to no original vertex. Its graph neighbourhood is precisely $\{u_1,\dots ,u_n\}$.

For a nonempty finite simple graph, the upper bound copies an optimal proper vertex colouring to its Mycielski shadow vertices and gives the Mycielski apex a fresh colour. For the lower bound, suppose $\mu (G)$ uses $k=\chi (G)$ colours, with $w$ coloured $k$. Shadows avoid $k$. Replace colour $k$ at each original $v_i$ by $u_i$'s colour. Changed originals form an independent set; unchanged neighbours differ because $u_i{v}_j$ is an edge. This proper vertex colouring of $G$ uses $k-1$ colours, contradicting its chromatic number.^[ref]

The nonempty condition means $V(G)\ne \varnothing$, not $E(G)\ne \varnothing$. An edgeless $n$-vertex graph with $n\ge 1$ has chromatic number one; its Mycielskian is a star graph on $w,u_1,\dots ,u_n$ together with $n$ isolated vertices, and needs two colours. If $G$ has no vertices, $\mu (G)$ is a single vertex, so the same formula also holds with the convention $\chi (G)=0$.

A finite simple graph $G$ is a triangle-free graph if and only if its Mycielskian is a triangle-free graph. No triangle in a graph can contain the Mycielski apex, whose neighbours are an independent set, or two Mycielski shadow vertices. A triangle in a graph containing one shadow $u_i$ and two originals $v_j,v_{\ell }$ requires all three original edges $v_i{v}_j,v_i{v}_{\ell },v_j{v}_{\ell }$, hence an original triangle in a graph. Conversely every original triangle in a graph remains. In fact each original triangle in a graph gives four in $\mu (G)$: itself and the three choices of replacing one of its vertices by its shadow. Thus triangle-freeness is preserved, but a positive triangle count is multiplied by four.

Define $M_2=K_2$ and $M_{k+1}=\mu (M_k)$ for $k\ge 2$. By the Mycielskian chromatic increase and Mycielskian triangle preservation, each $M_k$ is a finite triangle-free graph with chromatic number $k$. The first steps are $K_2,C_5$, the Grötzsch graph, and then a 23-vertex graph needing five colours. The vertex recurrence $n_{k+1}=2n_k+1$ gives $n_k=3\cdot 2^{k-2}-1$. These explicit examples show how arbitrarily strong graph coloring constraints can accumulate without any three-vertex clique.

For every $g,k\ge 3$, there is a finite graph with no cycle of length at most $g$ and with chromatic number at least $k$. A probabilistic proof samples a sparse binomial random graph, observes that it has few short cycles and no large independent set, and deletes one vertex from every short cycle.

A connected graph of maximum degree $\Delta$ has chromatic number at most $\Delta$ unless it is a complete graph or an odd cycle.

The edge chromatic number is the least number of colours required to colour edges so that incident edges receive different colours.

An $r$-regular graph with $r\ge 2$ and a bridge in a graph separating an odd number of vertices from the rest cannot have an $r$-colour proper edge colouring. Such a colouring would partition the edges into $r$ perfect matchings. Each perfect matching must cross the odd-sided cut of a graph, so each would have to contain its unique crossing edge, the bridge in a graph. An edge cannot belong to two colour classes.

For odd $r$, every bridge in a graph in an $r$-regular graph automatically has odd-sized sides: if $S$ is either resulting connected component of a graph, double counting gives $r|S|=2|E(S)|+1$, so parity forces $|S|$ odd. Thus an odd-$r$ regular graph with a bridge in a graph is a class two regular graph.

For every finite bipartite graph, the edge chromatic number equals its maximum degree. Repeatedly remove a matching covering maximum-degree vertices in a bipartite graph: each removal reduces the maximum degree by at least one. The removed matchings in a graph are colour classes of a proper edge colouring. The reverse bound follows from the distinct colours required at a vertex of maximum degree.

Every finite simple graph of maximum degree $\Delta$ has edge chromatic number $\Delta$ or $\Delta +1$.

In a partial proper edge colouring with one uncoloured edge incident with a vertex $x$, a Vizing fan is a sequence of neighbours of $x$ whose incident edge colours are missing at earlier fan vertices. With one more colour than the maximum degree, fan rotations and a two-colour Kempe chain free one common colour at the endpoints of the uncoloured edge.

For two colours in a proper graph colouring, a Kempe chain is a connected component of the subgraph using only those colours. Interchanging the two colours throughout one component preserves properness.

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 $G$ and a positive integer $t$, $P_G(t)$ is the number of proper vertex colorings using a fixed, distinguished palette of $t$ colours. A colouring need not use every available colour, and exchanging two palette colours generally gives a different colouring. Although $P_G$ is a polynomial, its values at arbitrary noninteger arguments are not counts of colourings.

Consider the three-vertex path graph $A$--$B$--$C$. Choose $A$ in $t$ ways, then $B$ in $t-1$ ways, then $C$ in $t-1$ ways: $A$ and $C$ may agree because they are not adjacent. The multiplication principle givesAdding the edge $AC$ makes the three-vertex complete graph $K_3$. Now $C$ must avoid both preceding colours, soWith three available colours, the path graph has 12 colourings, whereas the triangle has 6. With two colours the counts are $2$ and $0$: the extra constraint makes the triangle impossible to colour.

For a nonempty graph, the chromatic number records only the first positive integer $t$ for which $P_G(t)>0$. The chromatic polynomial also counts the choices for every larger palette. For the path the chromatic number is $2$, and for the triangle it is $3$. 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 $t$ 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 $n\ge 1$ vertices and $m$ edges, its leading terms are $t^n-m{t}^{n-1}$; 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 $t(t-1{)}^3$.

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.

If a unicyclic graph has $n$ vertices and its unique graph cycle has length $\ell$, each of its $n-\ell$ off-graph cycle vertices contributes a factor $x-1$ after its parent in a rooted tree is coloured. Thus $p_G(x)=(x-1{)}^{n-\ell }{p}_{C_{\ell }}(x)$. Substituting the chromatic polynomial of a cycle yields the displayed formula, equivalently by repeated application of the chromatic polynomial after attaching a leaf.

For a cycle graph of length $\ell \ge 3$, the chromatic polynomial is $p_{C_{\ell }}(x)=(x-1{)}^{\ell }+(-1{)}^{\ell }(x-1)$. The graph triangle gives the base case $x(x-1)(x-2)$. For $\ell \ge 4$, the deletion-contraction recurrence for the chromatic polynomial gives $p_{C_{\ell }}(x)=x(x-1{)}^{\ell -1}-p_{C_{\ell -1}}(x)$, since deleting an edge leaves a path graph and contracting it gives the shorter cycle graph. Substitution proves the formula by mathematical induction.

For a finite simple graph on $n$ vertices with $m$ edges and no graph cycle shorter than $\ell$, the coefficient of $x^{n-i}$ in its chromatic polynomial is $(-1{)}^i(\genfrac{}{}{0ex}{}{m}{i})$ for $0\le i\le \min (n,\ell -2)$. In the chromatic polynomial inclusion-exclusion formula, an edge subset containing a graph cycle of length at least $\ell$ has $n-c(F)\ge \ell -1$. Thus every contribution to $x^{n-i}$ in this range is a forest, with exactly $i$ edges. Conversely, all $i$-edge subsets are forests, so precisely $\left(\genfrac{}{}{0ex}{}{m}{i}\right)$ terms contribute, each with sign $(-1{)}^i$.

Here $c(F)$ is the number of connected components of a graph in the spanning subgraph $(V(G),F)$, including isolated vertices. Apply the inclusion-exclusion principle to the conditions that the endpoints of an edge have equal colours. Imposing all such conditions for $F$ forces a single colour on each connected component of a graph, yielding $x^{c(F)}$ for positive integer $x$. The equality extends to a polynomial identity.

For connected components of a graph $G_1,\dots ,G_t$ of a finite graph $G$, choices of proper vertex colourings on different connected components of a graph are independent. The multiplication principle gives $p_G(x)={\prod }_j{p}_{G_j}(x)$. Each nonempty factor is divisible by $x$, hence $x^t$ divides the chromatic polynomial. The vanishing constant term follows by mathematical induction from the deletion-contraction recurrence for the chromatic polynomial, starting with $p_H(x)=x^{|V(H)|}$ for a nonempty graph without edges.

If a simple graph has the same chromatic polynomial as the Turán graph $T_r(n)$, it has the same number of vertices and edges, and the same chromatic number $r$. It is therefore $K_{r+1}$-free and attains equality in Turán's theorem. The equality case forces it to be isomorphic to $T_r(n)$.

Deleting an edge removes one colour constraint. Edge contraction describes exactly the newly admitted colourings that violate that constraint. If $e$ joins distinct vertices $u,v$ of a simple graph $G$, write $G-e$ for the graph with that edge deleted and $G/e$ for the graph with $u,v$ identified and $e$ removed. Parallel edges produced by the contraction may be reduced to one edge, since they impose the same condition on a proper vertex coloring. ThenTo see why, divide the proper vertex colorings of $G-e$ into two classes. Those with different colours at $u,v$ are exactly the colourings of $G$. Those with equal colours at $u,v$ correspond one-to-one to colourings of $G/e$: the merged vertex receives their common colour. Subtracting the second class leaves the first.

For the triangle, delete $AC$ to get a three-vertex path graph, or contract $AC$ to get two vertices joined by an edge after removing the redundant parallel edge. Consequently,At $t=3$, this says $6=12-6$. Of the twelve path colourings pictured above, six give $A,C$ the same colour; these are precisely the ones ruled out when we restore $AC$.

This recurrence is useful because it reduces a constrained counting problem to smaller graphs. A graph on $n$ vertices with no edges has $P_G(t)=t^n$, since every vertex chooses its colour independently. Repeated edge deletion and edge contraction reduce to this case and show that the counting function is a polynomial. The same recurrence gives its leading coefficients. The method is conceptually simple, although the number of recursive cases can still grow rapidly.

Attaching a new vertex that is a leaf of a graph multiplies the chromatic polynomial by $t-1$: after colouring the old graph, the new vertex may receive any colour except its neighbour's. Starting with one vertex and repeatedly adding a leaf of a graph constructs any finite tree. Thus a tree with $n\ge 1$ vertices hasIn contrast, every pair of vertices in a complete graph must receive different colours, so the multiplication principle gives the falling factorialFor positive integers $t<n$ this product vanishes, expressing the impossibility of assigning distinct colours to all $n$ vertices.