Graph Colorings and Polynomials

If the degree of each vertex of a graph is at most $d$, then the graph can be properly colored with $d+1$ colors.

If in a connected graph the degree of each vertex is at most $d$ and there is a vertex of degree less than $d$, then the graph can be properly colored with $d$ colors.

If in a connected graph the degree of each vertex is at most $d$ and there is a vertex whose removal makes the graph disconnected, then the graph can be properly colored with $d$ colors.

If a connected graph with more than two vertices splits, upon the removal of some edge, into two graphs each of which can be properly colored with $d$ colors, then the original graph can also be properly colored with $d$ colors.

In a connected graph the degree of each vertex is at most three. It is known that the graph can be properly colored with 3 colors so that the neighbors of some vertex all have the same color. One vertex and the edges emanating from it were added so that the degrees of all vertices are still at most three. Prove that the resulting graph can be properly colored with 3 colors.

In a connected graph the degree of each vertex is at most three. It is known that the graph can be properly colored with 3 colors and that in any such coloring every vertex has neighbors of different colors. One vertex and the edges emanating from it were added so that the degrees of all vertices are still at most three and the resulting graph is different from $K_{4}$. Prove that the resulting graph can be properly colored with 3 colors.

Brooks’ theorem. If the degree of each vertex of a graph is at most $d \geq 3$ and there is no $(d+1)$-clique, then the graph can be properly colored with $d$ colors.

If a graph cannot be properly colored with $k-1$ colors, then for any proper coloring of it with $k$ colors there exists a path containing exactly one vertex of each color.

If the longest of the paths in a graph that pass through each of their vertices only once passes through $d$ vertices, then the graph can be properly colored with $d$ colors.

If the longest odd non-self-intersecting cycle in a graph passes through $d-1$ vertices, then the graph can be properly colored with $d$ colors.

If the degree of every vertex of a graph does not exceed $d$, then the edges of the graph can be properly colored with $d+1$ colors.

There exists a coloring of the edges of the graph $K_{m,n}$ with two colors such that the number of monochromatic subgraphs $K_{a,b}$ is at most $\binom {m}{a}\binom {n}{b}2^{1-ab}$.

By how much can the chromatic number of a graph change if one edge is added to the graph? Or, formally, find all integers $k$ for which there exist a graph $G$ and an edge $u$ of it such that $\chi (G) - \chi (G-u) = k$.

$\chi (V, E_{1} \cup E_{2}) \leq \chi (V, E_{1})\chi (V, E_{2})$. (Recall that $(V, E)$ denotes the graph with vertex set $V$ and edge set $E$.)

For any $r_{1}, r_{2} \in \mathbb {N}$ construct graphs $(V, E_{1})$ and $(V, E_{2})$ such that $\chi (V, E_{1} \cup E_{2}) = \chi (V, E_{1})\chi (V, E_{2})$, $\chi (V, E_{1}) = r_{1}$, and $\chi (V, E_{2}) = r_{2}$.

The vertices of an arbitrary graph $G$ can be numbered so that the greedy algorithm for coloring it uses exactly $\chi (G)$ colors.

For each integer $k > 0$ construct a bipartite graph and a numbering of its vertices such that the coloring of the graph produced by the greedy algorithm corresponding to the constructed numbering has at least $k$ colors.

the complete graph;

the graph having no edges;

the path;

the cycle;

a tree

$\chi_{G} = \chi_{G-u} - \chi_{G/u}$ for every edge $u$ of the graph $G$.

Birkhoff–Whitney theorem. For every graph $G$ there exists exactly one polynomial such that for every $t$ the number $\chi_{G}(t)$ of proper colorings of the graph $G$ with $t$ colors equals the value of this polynomial at the point $t$.

The degree of the chromatic polynomial $\chi_{G}$ equals $n$, the leading coefficient equals 1, the second coefficient equals $(-e)$, and the coefficients alternate in sign (i.e., the coefficient of $t^{n-2k}$ is nonnegative and the coefficient of $t^{n-2k+1}$ is nonpositive for every integer $k$).

The third coefficient of the chromatic polynomial of a graph, counting from the leading one, is uniquely determined by the collection of subgraphs of the graph containing 3 vertices.

The number $\left|\chi_{G}(-1)\right|$ equals the number of acyclic orientations of the graph $G$, i.e., the number of ways to put arrows on its edges so that the resulting directed graph contains no directed cycles.

If the chromatic polynomial of a graph equals $t(t-1)^{n-1}$, then the graph is a tree.

There is no graph with chromatic polynomial $t^{4} - 3t^{3} + 3t^{2}$.

A path on $m$ vertices is ``attached'' by one of its ends to one of the vertices of a graph $G$ containing $n$ vertices. Express the chromatic polynomial of the resulting graph with $m+n-1$ vertices in terms of $\chi_{G}$.

If $H, K$ are the graphs into which a connected graph $G$ splits when one of its edges is deleted, then $t\chi_{G} = (t-1)\chi_{H}\chi_{K}$.

The function $\chi_{G}'$ is a polynomial in $t$.

The leading monomial of $\chi_{G}'$ equals $t^{e}$.

The coefficient of $t^{e-1}$ in $\chi_{G}'$ equals $-\sum_{v \in V(G)} \binom {\deg v}{2}$.

spanning forests in the graph $G$ (i.e., unions of spanning trees of its components);

sets of edges of the graph $G$ such that for every connected component of the graph the edges of the set lying in it form a connected subgraph;

subgraphs of the graph $G$ that are forests.

the number from part (1) of Problem 3.3.6;

the number from part (2) of Problem 3.3.6;

the number from part (3) of Problem 3.3.6;

the chromatic polynomial.