Let \(G\) be a graph of order \(n \geq 1\). Then

Moreover, \(\chi (G)=n\) if and only if \(G\) is a complete graph, and \(\chi (G)=1\) if and only if \(G\) is a null graph.

Let \(G\) be a graph with at least one edge. Then \(\chi (G) = 2\) if and only if \(G\) is bipartite.

Let \(G\) be a graph for which the maximum degree of a vertex is \(\Delta \). Then the greedy algorithm produces a \((\Delta +1)\)-coloring of the vertices of \(G\), and hence

Let \(G\) be a connected graph for which the maximum degree of a vertex is \(\Delta \). If \(G\) is neither a complete graph \(K_n\) nor an odd cycle graph \(C_n\), then \(\chi (G) \leq \Delta \).

Let \(T\) be a tree of order \(n\). Then

Let \(G\) be a graph of order \(n \geq 1\). Then the number of \(k\)-colorings of \(G\) is a polynomial in \(k\) of degree equal to \(n\) (with leading coefficient equal to \(1\)) and this polynomial-the chromatic polynomial of \(G\)-is computed correctly by the preceding algorithm.

Let \(G\) be a graph and assume that \(G\) contains a subgraph \(H\) equal to a complete graph \(K_r\). Then the chromatic polynomial of \(G\) is divisible by the chromatic polynomial \([k]_r\) of \(K_r\).

Let \(U\) be an articulation set of \(G\) and suppose that the induced subgraph \(G_U\) is a complete graph \(K_r\). Let the connected components of \(G_{V-U}\) be the induced subgraphs \(G_{U_1}, \ldots , G_{U_t}\). For \(i=1, \ldots , t\), let \(H_i=G_{U \cup U_i}\) be the subgraph of \(G\) induced by \(U \cup U_i\). Then

In particular, the chromatic number of \(G\) is the largest of the chromatic numbers of \(H_1, \ldots , H_t\).

Let \(G\) be a plane-graph of order \(n\) with \(e\) edge-curves and assume that \(G\) is connected. Then the number \(r\) of regions into which \(G\) divides the planr satisfies

Let \(G\) be a connected planar graph. Then there is a vertex of \(G\) whose degree is at most \(5\).

A graph \(G\) is planar if and only if it does not have a subgraph that is a subdivision of a \(K_5\) or of a \(K_{3,3}\).

A graph \(G\) is planar if and only if it does not contain a subgraph that contracts to a \(K_5\) or a \(K_{3,3}\).

Let there be given a \(k\)-coloring of the vertices of a graph \(H=(U, F)\). Let two of the colors be red and blue, and let \(W\) be the subset of vertices in \(U\) that are assigned either the color red or the color blue. Let \(H_{r, b}\) be the subgraph of \(H\) induced by the vertices in \(W\) and let \(C_{r, b}\) be a connected component of \(H_{r, b}\). Interchanging the colors red and blue assigned to the vertices of \(C_{r, b}\), we obtain another \(k\)-coloring of \(H\).

The chromatic number of a planar graph is at most \(5\).

Hadwiger’s conjecture holds for \(p = 5\) if and only if every planar graph has a \(4\)-coloring.

Let \(p \leq 3\). If \(G\) is a connected graph with chromatic number \(\chi (G) \geq p\), then \(G\) can be contracted to a \(K_p\).

Let \(G\) be a connected graph of order \(n \geq 2\). Then

A graph \(G\) is \(\chi \)-perfect if and only if it is \(\theta \)-perfect. Equivalently, \(G\) is \(\chi \)-perfect if and only if \(\bar{G}\) is \(\chi \)-perfect.

Every interval graph is a chordal graph.

Let \(G=(V, E)\) be a connected graph and let \(U\) be an articulation set of \(G\) such that the subgraph \(G_U\) induced by \(U\) is a complete graph. Let the connected components of the induced subgraph \(G_{V-U}\) be \(G_1=\left(U_1, E_1\right), \ldots , G_t=\left(U_t, E_t\right)\). Assume that the induced graphs \(G_{U_2 \cup U}\) satisfy

Then

Let \(G = (V, E)\) be a connected chordal graph and let \(U\) be a minimal articulation set of \(G\). Then the subgraph \(G_U\) induced by \(U\) is a complete graph.

Every chordal graph is perfect.

Let \(G=(V, E)\) be a bipartite graph with bipartition \(X, Y\) with as sociated family \(\mathcal{A}_G\) of subsets of \(Y\). Let \(t\) be a positive integer. Then from a subfamily

we obtain a matching

Conversely, from a matching (12.11) of \(G\) of \(t\) edges, we get a subfamily (12.10) of \(\mathcal{A}_G\) of \(t\) sets with \(\left(e_{i_1}, e_{i_2}, \ldots , e_{i_t}\right)\) as \(S D R\). Thus the largest number of sets in a subfamily of \(\mathcal{A}_G\) with an \(S D R\) equals thr matching number \(\rho (G)\) of \(G\).

Let \(G = (V, E)\) be a graph. Then a subset \(W\) of the set \(V\) of vertices is a cover if and only if the complementary set of vertices \(V \setminus W\) is an independent set.

Let \(G=(V, E)\) be a bipartite graph. Then

that is, the largest number of edges in a matching equals the smallest number of vertices in a cover.

Let \(G=(V, E)\) be a graph. Then \(G\) has a perfect matching if and only if

that is, removing a set of vertices does not create more odd components than the number of vertices removed.

Let \(G(V, E)\) be a graph with \(n\) vertices. Then

where the minimum is taken over all \(U \subseteq V\).

Let \(G\) be a graph of order \(n\). Then

with equality on the left if and only if \(G\) is disconnected and with equality on the right if and only if \(G\) is a complete graph.

For each graph \(G\), we have

Let \(G\) be a graph of order \(n \geq 3\). Then the following three assertions are equivalent: (1) \(G\) is 2-connected. (2) \(G\) is connected and does not have an articulation vertex. (3) For each triple of vertices \(a, b, c\), there is a path joining a and b that does not contain \(c\).

Let \(G=(V, E)\) be a connected graph of order \(n \geq 2\), and let

be the blocks of \(G\). Then \(E_1, E_2, \ldots , E_r\) is a partition of the set \(E\) of edges of \(G\), and each pair of blocks has at most one vertex in common.

Let \(G = (V, E)\) be a graph of order \(n \geq 3\). Then \(G\) is \(2\)-connected if and only if, for each pair \(a, b\) of distinct vertices, there is a cycle containing both \(a\) and \(b\).

Let \(k\) be a positive integer and let \(G\) be a graph of order \(n \geq k +1\). Then \(G\) is \(k\)-connected if and only if, for each pair \(a, b\) of distinct vertices, there are \(k\) paths joining \(a\) and \(b\) such that each pair of paths has only the vertices \(a\) and \(b\) in common.