Colorings of Graphs

Prove that a graph is $k$-colorable if and only if each block in it is $k$-colorable.

Show that every planar graph is 6-colorable.

Show that every planar graph is 5 -colorable.

Prove Theorem 9.1: $\chi (G) \leq \Delta (G)+1$ for any graph $G$.

Show that for any graph $G, \chi (G) \leq 1+\max \delta \left(G^{\prime }\right)$, where the maximum is taken over all induced subgraphs $G^{\prime }$ of $G$.

Prove Theorem 2 (Brooks's theorem): If $G$ is a connected graph that is neither a complete graph nor an odd cycle, $\chi (G) \leq \Delta (G)$.

Prove that if the vertex set $V=\left\{ v_{1}, v_{2}, \ldots , v_{n}\right\}$ of a graph $G$ has the nonincreasing degree sequence $d_{1} \geq d_{2} \geq \ldots \geq d_{n}, \chi (G) \leq \max_{i} \min \left\{ d_{i}+1, i\right\}$.

Show that the number of colors needed to color the vertices of $G$ using the largest first searching method does not exceed $1+\Delta (G)$.

Use the largest first algorithm to color the vertices of the graph shown in Fig. 9-10.

A $k$-chromatic graph $G$ is said to be a critically $k$-chromatic (or a $k$-critical) graph if $\chi (G-v)= k-1$ for every vertex $\nu$ of $G$. Show that a critically $k$-chromatic graph $G$ is a block.

Give an example of a $k$-chromatic graph that is not critically $k$-chromatic.

Characterize critically $k$-chromatic graphs when $k=2$ and $k=3$.

A $k$-chromatic graph $G$ is said to be a minimally $k$-chromatic graph $\chi (G-e)=k-1$ for every edge $e$ of $G$. Give an example of:

Show that a $k$-chromatic graph contains a critically (minimally) $k$-chromatic graph.

Show that if $G$ is critically $k$-chromatic, $\delta (G) \geq (k-1)$. Give a counterexample to show that the converse does not hold.

Give an example of a $k$-chromatic graph $G$ for which the inequality $\delta (G) \geq (k-1)$ is not valid.

Prove that a $k$-chromatic graph $G$ has at least $k$ vertices of degree at least $k-1$.

Use the inequality obtained in Problem 9.15 to prove the Szekeres-Wilf theorem (Problem 9.51).

Prove that a critically $k$-chromatic graph $G$ with exactly one vertex whose degree exceeds $(k-1)$ is minimally $k$-chromatic.

Show that if $G=(V, E)$ is a graph with $\chi (G) \geq k$ and with a vertex partition $(X, Y)$ of $V$ such that the subgraphs $G(X)$ and $G(Y)$ induced by $X$ and $Y$, respectively, are $(k-1)$-colorable, cut $[X, Y]$ consisting of those edges in $E$ joining vertices in $X$ and vertices in $Y$ has at least $(k-1)$ edges.

Show that a critically $k$-chromatic graph $G$ is $(k-1)$-edge connected. [Equivalently, any connected minimally $k$-chromatic graph is $(k-1)$-edge connected.] Give an example to show that the converse is not true.

Show that if $G$ is a critically $k$-chromatic graph, there are no subgraphs $G_{1}$ and $G_{2}$ such that $G=G_{1} \cup G_{2}$ and, at the same time, such that $G_{1} \cap G_{2}$ is complete.

Show that the graph induced by a separating set $W$ of vertices of a critically $k$-chromatic graph is not a complete graph. In particular, if $\left|W\right|=2$, the two vertices in $W$ are not adjacent.

Give an example of a graph $G$ with a separating set $W$ consisting of two adjacent vertices.

If a minimally $k$-chromatic graph $G$ has a separating set $W$ consisting of two vertices $u$ and $v$, show that:

Illustrate Dirac's theorem in the case of the graph shown in Fig. 9-13(a).

Show that if a minimally $k$-chromatic graph has a separating set consisting of two vertices, the sum of their degrees is at least $(3 k-5)$.

Use the inequality obtained in Problem 9.27 to prove that $\chi (G) \leq \Delta (G)$, where $G$ is a connected graph that is neither a complete graph nor an odd cycle in the special case when $G$ is not 3 -connected. (This is a part of Brooks's theorem.)

A $k$-chromatic graph $G$ is uniquely colorable if any $k$-coloring of $G$ induces the same partition of the vertex set of $G$

Show that if a $k$-chromatic graph $G$ is uniquely colorable, the subgraph induced by the union of any two sets in the vertex partition in a coloring is a connected graph.

Show that if a $k$-chromatic graph $G$ is uniquely colorable, it is $(k-1)$-connected.

Show that any 4-chromatic uniquely colorable planar graph $G$ is a maximal planar graph.

Show that the graph obtained from a triangle-free $k$-chromatic graph by the Mycielski method is a triangle-free $(k+1)$-chromatic graph.

Find $P(G, x)$, where $G$ is a cyclic graph with $n$ vertices where $n=3$ or $n=4$.

If $e$ is an edge of $K_{4}$, find the chromatic polynomial of $K_{4}-e$.

Show that if $G$ is the union of two graphs $G_{1}$ and $G_{2}$ that share a single vertex, the chromatic polynomial of $G$ is the product of the chromatic polynomials of $G_{1}$ and $G_{2}$ divided by $x$.

If $G$ is the connected graph obtained by linking two triangles so that they share one vertex in common, find the chromatic polynomial of $G$.

Obtain the chromatic polynomial of the graph shown in Fig. 9-15.

Fig. 9-15

Show that if $G$ is a graph of order $n$ and size $m$, the absolute value of the coefficient of $x^{n-1}$ in the chromatic polynomial is equal to the size of the graph.

Show that a graph of order $n$ is a tree if and only if its chromatic polynomial is equal to $x(x-1)^{n-1}$.

Use the reduction theorem proved in Problem 9.41 to compute $P(G, x)$ of graph $G$ in Problem 9.38.

The chromatic polynomial of a cyclic graph of order $n$ is $(x-1)^{n}+(-1)^{n}(x-1)$.

Prove that the sum of the coefficients of the chromatic polynomial of a graph that has at least one edge is 0.

Show that the coefficients of the chromatic polynomial alternate in sign.

Show that if $P(G, x)=x^{n}-a_{n-1} x^{n-1}+a_{n-2} x^{n-2}-a_{n-3} x^{n-3}+\cdots$ is the chromatic polynomial of a connected graph $G, 1<a_{n-1}<a_{n-2}<\cdots <a_{r}$, where $r$ is the floor of $(n / 2+1)$.

Show that if $P(G, x)=x^{n}-a_{n-1} x^{n-1}+a_{n-2} x^{n-2}-a_{n-3} x^{n-3}+\cdots$ is the chromatic polynomial of a connected graph $G, a_{i} \geq \binom { n-1}{r-1}$ for each $i$.

Show that the coefficient of $x$ in the chromatic polynomial of a connected graph is not zero.

Show that the smallest number $k$ such that the coefficient of $x^{k}$ is not zero in the chromatic polynomial of $G$ is the number of components.

Show that $x^{5}-7 x^{4}+9 x^{3}-3 x^{2}$ cannot be the chromatic polynomial of a simple graph.

The necessary conditions to be satisfied by the chromatic polynomial of a connected simple graph of order $n$ and size $m(m>0)$ are (1) it should be a polynomial in $x$ of degree $n$, (2) it is a monic polynomial, (3) the sum of the coefficients is zero, (4) the coefficients alternate in sign, (5) the constant term is zero, (6) the coefficient of $x$ is not zero, (7) the coefficient of $x^{n-1}$ is $-m$, and (8) the absolute values of the coefficients of $x^{n}, x^{n-1}, x^{n-2}, \ldots , x^{r}$ are strictly increasing, where $r$ is the floor of $(n / 2+1)$. Give an example of a polynomial that satisfies these eight conditions but is not the chromatic polynomial of a simple connected graph.

Show that if $G$ is a bipartite multigraph, its chromatic index is $\Delta (G)$. In particular, show that the chromatic index of the complete bipartite graph $K_{m, n}$ is the maximum of $\left\{ m, n\right\}$.

If a graduate student in a department has taken $k$ courses $(k \geq 0)$ taught by a professor in that department, the professor has to give $k$ oral examinations to the student at the end of the academic year. Each oral examination lasts exactly $t$ hours. Find the minimum time required to complete all the departmental oral examinations if we know the number of courses each student has taken taught by each professor.

A Latin square of order $n$ is an $n \times n$ matrix with entries from the set $\left\{ 1,2, \ldots , n\right\}$ such that no entry appears twice in the same row and no entry appears twice in the same column. Show that a Latin square of order $n$ can be constructed using an $n$ edge coloring of the complete bipartite graph $K_{n, n}$.

Show that if $G$ is the complete graph with $2 n$ vertices, its chromatic index is $2 n-1$.

Show that if $G$ is the complete graph with $2 n-1$ vertices, its chromatic index is $2 n-1$.

There are $2 n$ schoolgirls in a boardinghouse. Each morning they walk to school in groups of two, as doubles. Find the maximum number of consecutive morning walks they can undertake such that each girl forms a pair with every other girl exactly once during these walks.

There are 15 girls in a boardingschool who walk to school in groups of three (as triples) all seven days a week. Is it possible to form triples such that no two girls walk together more than once?

Prove Theorem 9.4 (Vizing's theorem): The chromatic index of a simple graph $G$ is either $\Delta (G)$ or $\Delta (G)+1$.

If $G$ is an $r$-regular simple graph with an odd number of vertices, show that its chromatic index is $r+1$. Is the converse true?

Let $G$ be a 3-colorable cubic graph whose edges are colored using the colors $c_{i}(i=1,2,3)$, and let $F$ be a cut set in $G$. If the number of edges with color $c_{i}$ in $F$ are $x_{i}$, show that the three numbers $x_{1}, x_{2}$, and $x_{3}$ are all even or all odd.

Prove Theorem 9.5: If a cubic graph has a bridge, its chromatic index is 4.

Let $G^{\prime }$ be the graph obtained from a cubic graph $G$ by contracting a triangle (a cycle of three vertices) in it into a single vertex. Show that $\chi^{\prime }(G)=3$ if and only if $\chi^{\prime }\left(G^{\prime }\right)=3$.

Let $e_{1}$ and $e_{2}$ be two edges with no vertex in common in a cubic graph $G$. Insert two vertices $x_{1}$ and $y_{1}$ on $e_{1}$ and two vertices $x_{2}$ and $y_{2}$ on $e_{2}$. Join $x_{1}$ and $x_{2}$ by an edge. Join $y_{1}$ and $y_{2}$ by an edge. If the chromatic index of the new graph $G^{\prime }$ thus constructed is 4, show that the chromatic index of $G$ also is 4.

Give a counterexample to show that the chromatic index of $G^{\prime }$ (in Problem 9.64) need not be 4 when the chromatic index of $G$ is 4.

Let $G$ be a cubic graph with a cut set $F$ consisting of three edges $e_{i}(i=1,2,3)$ joining vertices $u_{i}$ and $v_{i}$, where the six vertices are distinct such that $G-F$ has two subgraphs $H_{1}$ and $H_{2}$. Construct vertex $u$ in $H_{1}$, and join it to the three end-vertices in $H_{1}$ of the cut set, creating a new cubic graph $G_{1}$. Likewise, create another cubic graph $G_{2}$ by constructing vertex $\nu$ and joining it to the end-vertices in $H_{2}$ of the cut set. Show that the graph $G$ is 3 edge colorable if and only if both $G_{1}$ and $G_{2}$ are 3 edge colorable.

Let $G$ be a cubic bridgeless graph with a cut set $F$ consisting of two edges, edge $e_{1}$ joining $u_{1}$ and $v_{1}$ and edge $e_{2}$ joining $u_{2}$ and $v_{2}$, so that $G-F$ has two components $H_{1}$ and $H_{2}$. Assume that $u_{1}$ and $u_{2}$ are in one component. Join $u_{1}$ and $u_{2}$ by an edge in $H_{1}$, creating a cubic (multi) graph $G_{1}$. Likewise, create $G_{2}$ from $H_{2}$ by joining $v_{1}$ and $v_{2}$. Show that the graph $G$ is 3 edge colorable if and only if both $G_{1}$ and $G_{2}$ are 3 edge colorable.

A cut set $F$ in a graph $G$ is called a cyclic cutset if $G-F$ has two components, each of which has a cycle. The cyclic edge connectivity $\boldsymbol {\lambda }_{\boldsymbol {c}}(\boldsymbol {G})$ of $G$ is the cardinality of the smallest cyclic cut set in $G$, and $G$ is said to be cyclically $k$ edge connected if $\lambda_{c}(G) \geq k$. Show that the Petersen graph is cyclically 4 edge connected.

A snark, by definition, is an uncolorable, cyclically 4 edge connected cubic graph of girth at least 5. Show that this definition is more exclusive in the sense that a cubic bridgeless graph cannot be called a snark just because it is uncolorable. (The girth conjecture is the statement that every snark has a cycle consisting of five or six edges. This conjecture is now known to be false.)

Let $x$ and $y$ be any two adjacent vertices in a cubic graph $G$ of order $n$, where $x$ is also adjacent to $a$ and $b$. Likewise, $y$ is adjacent to $c$ and $d$. Four vertices $a, b, c$, and $d$ are assumed to be distinct. Let $e$ and $f$ be two independent edges in a cubic graph $G^{\prime }$ of order $n^{\prime }$, where $e$ joins vertices $p$ and $q$ and $f$ joins vertices $r$ and $s$. Delete $x$ and $y$ in $G$, and delete $e$ and $f$ from $G^{\prime }$. Then connect the two graphs by constructing four new edges joining $a$ and $p, b$ and $q, c$ and $r$, and $d$ and $s$. The graph thus constructed is called a dot product $\boldsymbol {G}. \boldsymbol {G}^{\prime }$ of the two graphs, and it is obviously a cubic graph of order $n+n^{\prime }-$ 2. Show that a dot product of two snarks is a snark.

A Blanusa snark is a dot product of the Petersen graph with itself. Construct a Blanusa snark.

Fig. 9-19

Show that a snark is not a Hamiltonian graph.

Give an example of a non-Hamiltonian cubic graph that is not a snark.

Give an example of a "nonsnark," a cyclically 4-connected nonplanar cubic graph, the edges of which can be colored using three colors.

Show that in any cubic map, there is at least one region with fewer than six boundary edges. (See also Solved Problem 8.16.)

Show that there exists an unavoidable set of four configurations, and list them.

Show that the first three graphs shown in Fig. 9-22 are reducible.

(Wernicke's Unavoidable Set) Show that the set consisting of the five graphs shown in Fig. 9-23 is an unavoidable set.

Fig. 9-23

Show that the Birkhoff diamond (see Fig. 9-24) is reducible.

Fig. 9-24

The flow ratio of a cycle $C$ in an orientation $D$ of a graph $G$ is the ratio $p / q$ (where $p \geq q \geq 0$ ), $p$ being the number of arcs in one direction and $q$ being the number of arcs in the opposite direction in $C$. Show that the vertices of a $G$ can be $k$-colored if and only if there is orientation $D$ of the graph in which the flow ratio of no cycle exceeds $(k-1)$.

Hajos's conjecture claims that every $k$-chromatic graph has a subgraph homeomorphic to the complete graph of order $k$. Show that the conjecture is true if $k \leq 4$.

Show that if Hajos's conjecture is true for $k=5$, the four-color theorem is true.

Show that Hajos's conjecture is false if $k \geq 7$.

Hadwiger's conjecture claims that every $k$-chromatic graph has a subgraph contractible to the complete graph of order $k$.

Prove that $\chi \left(S_{g}\right)=H(g)$, where $H(g)$ is the floor of $\frac{1}{2}\left\{ 7+ \sqrt{1+48 g}\right\}$ for any surface of positive genus $g$.

Show that a plane graph $G$ is 2-colorable if and only if the degree of each region in $G$ is even.

Show that a map is 2-colorable if and only if it is Eulerian.

A plane graph is 3-colorable if and only if it is a subgraph of a triangulation in which the degree of each vertex is even.

Show that:

The clique covering number $\boldsymbol {\theta }(\boldsymbol {G})$ (also known as the partition number) of a graph $G=(V, E)$ is the minimum number of pairwise disjoint cliques whose union is the set $V$. A graph $G$ is $\boldsymbol {\alpha }$-perfect if for every induced subgraph $H$ of $G, \theta (H)$ is equal to its internal stability number $\alpha (H)$. Show that a graph is perfect if and only if its complement is $\alpha$-perfect.

Show that the line graph of a bipartite graph $G$ is perfect.

A directed graph is a transitive digraph if whenever there is an arc from vertex $u$ to vertex $v$ and an arc from $v$ to vertex $w$, there is an arc from $u$ to $w$. A graph $G$ is a transitively orientable graph (also known as a comparability graph) if it is possible to orient its edges such that the resulting digraph is a transitive digraph. Show that a comparability graph is perfect.

Let $W$ be a set of vertices in a connected graph $G=(V, E)$ such that the subgraph induced by $W$ is complete and such that $G-W$ is a disconnected graph with components $G_{i}=\left(V_{i}, E_{i}\right)$, where $i= 1,2, \ldots , r$. Let $H_{i}$ be the subgraph induced by the union of $V_{i}$ and $W$ for each $i$. Show that if $\omega \left(H_{i}\right)=\chi \left(H_{i}\right)$ for each $i, \omega (G)=\chi (G)$.

Let $W$ be a set of vertices in a chordal graph $G$ such that $W$ is a minimal separating set. Show that the graph induced by $W$ is complete.

Prove that a chordal graph is perfect.

Show that a graph is perfect if and only if every induced subgraph $H$ has an independent set $W$ of vertices such that $\omega (H-W)<\omega (H)$.

Show that if the vertices of a perfect graph are "replaced" by perfect graphs, the resulting graph is perfect.

Show that if a graph $G$ is perfect, it has a clique that intersects with every maximum cardinality independent set in $G$.

Show that the complement of a perfect graph is perfect.

Show that a graph is perfect if and only if it is $\alpha$-perfect.

(Erdös's Theorem) If the graph $G=(V, E)$ does not contain $K_{k+1}$ as a subgraph, show that there exists a $k$-chromatic graph $H=(V, F)$ such that $\operatorname {deg}_{H}(v) \geq \operatorname {deg}_{G}(v)$ for every $v$ in $V$. (Graph $G$ is said to be degree-majored by graph $H$.)

(Turan Number and Turan Graph) Find a nondecreasing sequence of $k$ positive integers $a_{i}(i= 1,2, \ldots , k)$ whose sum is $n$ such that $\sum_{1 \leq i \leq j<k} a_{i} a_{j}$ is maximum.

Show that if a graph $G=(V, E)$ of order $n$ does not contain $K_{k+1}$ as a subgraph. $\left|E\right| \leq t(n, k)$.

Find the maximum number of edges in:

Find the chromatic number of a cubic nonbipartite graph.

Show that if $G$ is a $k$-critical graph of order $n$ and size $m,(k-1)(n) \leq 2 m$.

Show that if a $k$-chromatic graph $G$ is uniquely colorable, the subgraph induced by the union of any two or more subsets of a vertex partition defined by a $k$-coloring is $(k-1)$-connected.

Show that $\chi (G) \leq 1+n-\alpha (G)$.

Find the chromatic polynomial of $K_{1, n}$.

If $G$ is the connected graph obtained by linking a triangle and a cyclic graph of order 4 so that they share one vertex in common, find the chromatic polynomial of $G$.

If $G$ is a connected graph of order $n$, prove that $P(G, x) \leq x(x-1)^{n-1}$.

Show that Vizing's theorem need not be true if the graph under consideration is not simple.

Show that the four-color theorem is true if and only if the following condition holds: Every planar graph has an orientation such that the flow ratio of any cycle in the orientation is at most 3.

Show that Hadwiger's conjecture is true for $k=5$.

Show that any outerplanar graph is 3-colorable.

Show that a triangulation is 3-colorable if and only if the degree of each vertex in it is even.

The complement of a comparability graph is known as an incomparability graph. Show that an incomparability graph is both perfect and $\alpha$-perfect.

Show that the Petersen graph is not perfect.

Show that an interval graph is perfect.

Find the size of the largest: