Let \(G\) be a finite simple graph whose chromatic number is \(\chi (G) = k\). Then \(G\) contains a subgraph \(H\) that is \(k\)-critical, that is, \(H\) satisfies \(\chi (H) = k\) and \(\chi (H') \lt \chi (H)\) for every proper subgraph \(H' \subset H\).

Let \(G\) be a graph on a finite, nonempty vertex set, and suppose \(G\) is critical: every proper subgraph \(H \subset G\) satisfies \(\chi (H) \lt \chi (G)\). Then \(G\) is connected.

Let \(G\) be a finite \(k\)-critical graph, that is, a graph with chromatic number \(\chi (G) = k\) every proper subgraph of which has strictly smaller chromatic number. Then every vertex of \(G\) has degree at least \(k - 1\); equivalently, the minimum degree satisfies \(\delta (G) \ge k - 1\).

Let \(G\) be a finite simple graph whose chromatic number equals \(k\). Then \(G\) has at least \(k\) vertices of degree at least \(k-1\); that is, the number of vertices \(v\) with \(\deg _G(v) \ge k-1\) is at least \(k\).

Let \(G\) be a simple graph on a finite vertex set, and let \(\Delta (G)\) denote its maximum degree, that is, the largest number of neighbours of any vertex. Then the chromatic number of \(G\) satisfies \(\chi (G) \le \Delta (G) + 1\).

Let \(G\) be a finite connected graph that is critical, meaning that every proper subgraph \(H\) of \(G\) satisfies \(\chi (H) \lt \chi (G)\), where \(\chi \) denotes the chromatic number. Then no vertex cut of \(G\) is a clique: if \(S\) is a proper set of vertices whose deletion leaves \(G\) disconnected, then the vertices of \(S\) are not pairwise adjacent.

Let \(G\) be a critical graph on a finite, nonempty vertex set \(V\). Then \(G\) is connected, and no single vertex is a vertex cut of \(G\): for every \(v \in V\), deleting \(v\) leaves the graph connected.

Let \(G\) be a finite simple graph that is critical, meaning that every proper subgraph of \(G\) has strictly smaller chromatic number than \(G\). Suppose \(u\) and \(v\) are two distinct vertices such that \(\{ u,v\} \) is a vertex cut of \(G\), that is, deleting \(u\) and \(v\) leaves the remaining graph disconnected. Then \(u\) and \(v\) are not adjacent in \(G\).

Let \(G\) be a finite simple graph on a nonempty vertex set, with \(n\) vertices and \(m\) edges. If \(G\) admits a proper coloring using \(k\) colors, then

Let \(G\) be a finite simple graph. Suppose that every two odd cycles of \(G\) share a vertex; that is, for any two closed walks in \(G\) that are cycles of odd length, there is a vertex lying on both. Then the chromatic number of \(G\) satisfies \(\chi (G) \le 5\).

Let \(G\) be a finite simple graph on \(n\) vertices, and enumerate its vertices as \(v_1, v_2, \dots , v_n\) so that their degrees are arranged in non-increasing order, \(d(v_1) \ge d(v_2) \ge \dots \ge d(v_n)\). Then the chromatic number of \(G\) satisfies

Let \(G\) be a finite simple graph with \(m \geq 1\) edges. Then the chromatic number of \(G\) satisfies

Let \(G\) be a simple graph on a finite vertex set \(V\) with \(n = \left\lvert V\right\rvert \) vertices, and let \(G^{c}\) denote its complement, the graph on \(V\) in which two distinct vertices are adjacent precisely when they are non-adjacent in \(G\). Writing \(\chi \) for the chromatic number, the sum of the chromatic numbers of a graph and its complement satisfies

Let \(G\) be a finite simple graph. For an induced subgraph \(H\) of \(G\), write \(\delta (H)\) for its minimum degree (the least number of neighbours of any vertex of \(H\)). Then the chromatic number of \(G\) satisfies

where the maximum is taken over all induced subgraphs \(H\) of \(G\).

Let \(G\) be a finite simple graph whose chromatic number equals \(k\). Suppose \(G\) admits a proper colouring, using some number \(n\) of colours, in which every one of the \(n\) colour classes contains at least two vertices. Then \(G\) admits a proper colouring with exactly \(k\) colours in which, likewise, every colour class contains at least two vertices.

Let \(G\) be a finite simple graph on a nonempty vertex set. Then \(G\) is \(3\)-critical if and only if it is isomorphic to the cycle \(C_n\) for some odd integer \(n \ge 3\).

Let \(G\) be a finite graph on a nonempty vertex set. Then \(G\) is \(1\)-critical if and only if \(G\) is isomorphic to \(K_1\), the complete graph on a single vertex.

Let \(G\) be a simple graph on a finite, nonempty vertex set. Then \(G\) is \(2\)-critical if and only if \(G\) is isomorphic to the complete graph \(K_2\) on two vertices.

Let \(G\) be a finite simple graph on a nonempty vertex set, and let \(k\) be a natural number such that \(G\) is \(k\)-critical (that is, \(\chi (G) = k\) and \(\chi (H) \lt k\) for every proper subgraph \(H\) of \(G\)). Let \(S\) be a vertex cut of \(G\), i.e. a proper subset of the vertices whose deletion leaves \(G\) disconnected. Then the subgraph of \(G\) induced on \(S\) is not uniquely \((k-1)\)-colourable: there exist two colourings of this induced subgraph with \(k-1\) colours that induce different partitions of \(S\) into colour classes.

Let \(G\) be a critical graph on a finite, nonempty vertex set, so that \(\chi (H) \lt \chi (G)\) for every proper subgraph \(H\) of \(G\). Then for any two distinct vertices \(u\) and \(v\), the neighbourhood \(N(u)\) is not contained in the neighbourhood \(N(v)\).

Let \(G\) be a finite graph on a nonempty vertex set \(V\). If \(G\) is \(k\)-critical — that is, \(G\) has chromatic number \(\chi (G) = k\) and every proper subgraph \(H\) of \(G\) satisfies \(\chi (H) \lt \chi (G)\) — then \(G\) does not have exactly \(k+1\) vertices; that is, \(\left\lvert V\right\rvert \neq k+1\).

Let \(G\) and \(H\) be simple graphs on finite, nonempty vertex sets, and let \(G \vee H\) denote their join, the graph obtained from the disjoint union of \(G\) and \(H\) by adding every edge between a vertex of \(G\) and a vertex of \(H\). Then the chromatic number of the join is the sum of the chromatic numbers of the two factors:

Let \(G\) and \(H\) be simple graphs on finite, nonempty, disjoint vertex sets, and let \(G \vee H\) denote their join, the graph obtained from the disjoint union of \(G\) and \(H\) by adding an edge between every vertex of \(G\) and every vertex of \(H\). Recall that a graph is critical when every proper subgraph has strictly smaller chromatic number than the graph itself. Then \(G \vee H\) is critical if and only if both \(G\) and \(H\) are critical.

Let \(G_1\) and \(G_2\) be simple graphs on a common finite, non-empty vertex set, and suppose that each becomes \(k\)-critical once its isolated vertices are discarded, i.e. the subgraph induced on the non-isolated vertices of \(G_i\) is \(k\)-critical for \(i = 1, 2\). Suppose further that these two sets of non-isolated vertices have exactly one vertex \(v\) in common, and let \(vv_1\) be an edge of \(G_1\) and \(vv_2\) an edge of \(G_2\). Then the graph

obtained by deleting the edge \(vv_1\) from \(G_1\) and the edge \(vv_2\) from \(G_2\), forming the union of the two resulting graphs, and adjoining the edge \(v_1v_2\), is again \(k\)-critical.

For every natural number \(n\) with \(n = 4\) or \(n \ge 6\), there is a simple graph \(G\) on \(n\) vertices that is \(4\)-critical: its chromatic number is \(\chi (G) = 4\), and every proper subgraph \(H \subsetneq G\) satisfies \(\chi (H) \lt \chi (G)\).

Let \(G\) be a finite graph, let \(X\) be a set of its vertices with complement \(V \setminus X\), and let \(n\) be a natural number. Suppose that the subgraphs induced on \(X\) and on \(V \setminus X\) are each \(n\)-colourable, and that the edge cut between the two parts contains fewer than \(n\) edges — that is, the number of edges having one endpoint in \(X\) and the other in \(V \setminus X\) is at most \(n-1\). Then \(G\) is itself \(n\)-colourable.

Let \(G\) be a finite graph on a nonempty vertex set, and let \(k\) be a natural number. If \(G\) is \(k\)-critical — that is, \(G\) has chromatic number \(k\) and every proper subgraph of \(G\) has strictly smaller chromatic number — then the edge connectivity of \(G\) satisfies \(\kappa '(G) \ge k - 1\); equivalently, \(G\) is \((k-1)\)-edge-connected.

Let \(G\) be a connected simple graph on a finite, nonempty vertex set that is neither a complete graph nor isomorphic to a cycle of odd length. Then the chromatic number of \(G\) is at most its maximum degree, \(\chi (G) \le \Delta (G)\).

The following two statements are equivalent. (i) (Brooks’ theorem) Every finite nonempty connected graph \(G\) that is neither a complete graph nor an odd cycle satisfies \(\chi (G) \le \Delta (G)\), where \(\chi (G)\) denotes the chromatic number and \(\Delta (G)\) the maximum degree. (ii) For every integer \(k \ge 4\), every finite nonempty \(k\)-critical graph \(G\) that is not complete satisfies \(\nu (k-1) + 1 \le 2\varepsilon \), where \(\nu \) is the number of vertices and \(\varepsilon \) the number of edges of \(G\).

Let \(G\) be a finite simple graph whose maximum degree \(\Delta (G)\) equals \(3\). Then the line graph of \(G\) — the graph whose vertices are the edges of \(G\), two being adjacent when they share an endpoint — has chromatic number at most \(4\).

(Dirac, 1953.) Let \(G\) be a finite, nonempty \(k\)-critical graph, and let \(u \neq v\) be two vertices for which \(\{ u,v\} \) is a \(2\)-vertex cut of \(G\). Then \(G - \{ u,v\} \) has two distinct components \(C_1\) and \(C_2\) whose \(\{ u,v\} \)-components \(G_1 = G[C_1 \cup \{ u,v\} ]\) and \(G_2 = G[C_2 \cup \{ u,v\} ]\) together make up all of \(G\), that is \(G = G_1 \cup G_2\); here \(G_1\) is of type \(1\) (every \((k-1)\)-colouring of \(G_1\) assigns \(u\) and \(v\) the same colour) and \(G_2\) is of type \(2\) (every \((k-1)\)-colouring of \(G_2\) assigns \(u\) and \(v\) different colours). Moreover, the graph \(G_1 + uv\) obtained by adding the edge \(uv\) to \(G_1\) and the graph \(G_2 \cdot uv\) obtained by identifying \(u\) and \(v\) in \(G_2\) are both \(k\)-critical.

Let \(G\) be a finite, nonempty \(k\)-critical graph, and let \(u,v\) be two distinct vertices such that \(\{ u,v\} \) is a vertex cut of \(G\), meaning that deleting \(u\) and \(v\) leaves the remaining graph disconnected. Then the degrees of \(u\) and \(v\) satisfy

equivalently \(d(u) + d(v) \ge 3k - 5\).

Let \(G\) be a finite simple graph whose chromatic number equals \(4\). Then \(G\) contains a subdivision of \(K_4\): there are four distinct branch vertices joined pairwise by six paths that are internally disjoint from one another and internally avoid all four branch vertices.

Let \(G\) be a finite simple graph on at least four vertices in which at most one vertex has degree less than \(3\). Then \(G\) contains a subdivision of \(K_4\).

Let \(G\) be a finite simple graph with \(n \ge 4\) vertices and at least \(2n - 2\) edges. Then \(G\) contains a subdivision of \(K_4\): four distinct branch vertices, joined in pairs by six paths that are internally disjoint from one another and whose interiors avoid all four branch vertices.

Let \(G\) be a finite simple graph, let \(u\) and \(v\) be adjacent vertices of \(G\), and let \(k\) be a natural number. Writing \(\pi _k(H)\) for the number of proper \(k\)-colourings of a graph \(H\), let \(G - uv\) be the graph obtained from \(G\) by deleting the edge \(uv\), and let \(G \cdot uv\) be the graph obtained by contracting that edge, i.e. by identifying \(u\) and \(v\) into a single vertex. Then

Let \(G\) be a finite simple graph on a nonempty vertex set, and write \(n\) for the number of its vertices and \(\pi _k(G)\) for the number of distinct proper \(k\)-colourings of \(G\). Then there is a polynomial \(p \in \mathbb {Z}[x]\) with integer coefficients such that \(p(k) = \pi _k(G)\) for every \(k \in \mathbb {N}\); moreover \(p\) has degree \(n\), leading coefficient \(1\), and constant term \(0\), and its coefficients alternate in sign, in the sense that \((-1)^{n-i}\, a_i \ge 0\) for every \(i\), where \(a_i\) denotes the coefficient of \(x^i\) in \(p\).

Let \(G\) be a finite simple graph on a nonempty vertex set \(V\), with \(\nu = |V|\) vertices and \(\varepsilon \) edges, and let \(\pi _k(G)\) denote the number of proper \(k\)-colourings of \(G\). If \(p \in \mathbb {Z}[x]\) is a polynomial with integer coefficients satisfying \(p(k) = \pi _k(G)\) for every natural number \(k\), then the coefficient of \(x^{\nu - 1}\) in \(p\) equals \(-\varepsilon \).

Let \(G\) be a tree on a finite, nonempty vertex set with \(\nu \) vertices, and let \(k\) be a nonnegative integer. Then the number of distinct proper \(k\)-colourings of \(G\) is

Let \(G\) be a connected simple graph on a finite, nonempty vertex set of size \(\nu \), and let \(k\) be a natural number. Writing \(\pi _k(G)\) for the number of distinct proper \(k\)-colourings of \(G\), one has

and moreover, if \(k \ge 3\), then equality \(\pi _k(G) = k(k-1)^{\nu -1}\) holds if and only if \(G\) is a tree.

Let \(n \ge 3\), let \(C_n\) denote the cycle graph on \(n\) vertices, and let \(k\) be a nonnegative integer. Then the number of distinct proper \(k\)-colourings of \(C_n\) is

Let \(G\) be a finite graph, and let \(\pi _k(H)\) denote the number of distinct proper \(k\)-colourings of a graph \(H\). Write \(G \vee K_1\) for the join of \(G\) with a single vertex — the graph obtained from \(G\) by adjoining one new vertex and joining it to every vertex of \(G\). Then for every integer \(k \ge 1\),

Let \(n \ge 3\) and \(k \ge 1\) be integers, and let \(W_n = C_n \vee K_1\) be the wheel with \(n\) spokes, obtained from the cycle \(C_n\) on \(n\) vertices by adjoining a single hub vertex joined to every vertex of the cycle. Writing \(\pi _k(W_n)\) for the number of distinct proper \(k\)-colourings of \(W_n\), one has

Let \(G\) be a finite simple graph and \(k\) a natural number, and write \(\pi _k(G)\) for the number of proper \(k\)-colourings of \(G\). Then

where the product ranges over the connected components \(C\) of \(G\) and \(G[C]\) denotes the subgraph of \(G\) induced on the vertex set of \(C\).

Let \(G\) be a simple graph on a finite vertex set, and let \(G'\) and \(H'\) be two subgraphs of \(G\); write \(\pi _k(\cdot )\) for the number of distinct proper colourings of a graph with \(k\) available colours, and regard each of \(G'\), \(H'\), their join \(G' \cup H'\), and their meet \(G' \cap H'\) as a graph on its own vertex set. Suppose the intersection \(G' \cap H'\) is complete, that is, every two of its vertices are adjacent in it. Then for every \(k \in \mathbb {N}\),

where \(G' \cup H'\) is written for the join.

Let \(G\) be a nonempty finite simple graph on \(\nu \) vertices, and for a natural number \(k\) write \(\pi _k(G)\) for the number of proper \(k\)-colourings of \(G\). Suppose \(p\) is a real polynomial that agrees with this count at every natural number, in the sense that \(p(k) = \pi _k(G)\) for all \(k \in \mathbb {N}\). Then every real root of \(p\) is at most \(\nu \); that is, if \(p(x) = 0\) with \(x \in \mathbb {R}\), then \(x \le \nu \).

For every positive integer \(k\), there exists a finite simple graph \(G\) that contains no triangle and whose chromatic number is exactly \(k\).

For every integer \(k \ge 2\), the graph \(G_k\) in the Mycielski tower is \(k\)-critical: its chromatic number is \(\chi (G_k) = k\), and it is critical, meaning that every proper subgraph \(H \subsetneq G_k\) satisfies \(\chi (H) \lt \chi (G_k)\).

Let \(k \ge 2\) be an integer, and let \(G\) be a finite graph on a nonempty vertex set whose chromatic number equals \(k\) and whose girth is at least \(6\). Then there exists a finite graph \(H\) whose chromatic number is at least \(k+1\) and whose girth is at least \(6\).

For every integer \(k \ge 2\), there exists a finite simple graph \(H\) whose chromatic number is at least \(k\) and whose girth is at least \(6\); that is, \(H\) cannot be properly colored with fewer than \(k\) colors, yet every cycle in \(H\) has length at least \(6\).

Let \(G\) be a finite simple graph and let \(k\) be a natural number. If \(G\) is \(k\)-colourable, then \(G\) admits a canonical colouring consisting of at most \(k\) colour classes; that is, there is a list \((V_1, V_2, \dots , V_m)\) of pairwise disjoint sets of vertices with \(m \le k\), whose union is the whole vertex set, in which each \(V_i\) is a maximal independent set of \(G\) among the vertices left uncoloured by \(V_1, \dots , V_{i-1}\).