Math Problems Vault

Problem 3.2.1

The chromatic number $\chi (G)$ of a graph $G$ is the minimum number of colors with which the vertices of the graph $G$ can be properly colored.

If deleting any vertex from the graph decreases the chromatic number, then $\chi (G) \leq 1 + \left[2e/n\right]$ .

?

Problem 3.2.2

(1)(2)(3)

The chromatic number $\chi (G)$ of a graph $G$ is the minimum number of colors with which the vertices of the graph $G$ can be properly colored.

?

(1)

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$ .

(2)

$\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$ .)

(3)

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}$ .

Problem 3.2.3

(1)(2)

The following algorithm for coloring the vertices of a graph is called greedy. First, all vertices are numbered arbitrarily. After that, successively, starting from the first one, each vertex is colored with the color of the smallest number that is absent among the already colored neighbors of this vertex.

?

(1)

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

(2)

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.

Remark.

?

This problem shows that the ``quality'' of the coloring produced by the greedy algorithm depends heavily on the ordering of the vertices.

Problem 3.2.4

Investigate for planarity (see Sec. 2.4), and find the chromatic number and the chromatic index of the graphs in Figs. 11 and 12.

The chromatic index of a graph is the minimum number of colors with which the edges of this graph can be properly colored.

Fig. 11. The Petersen graph

Fig. 12. Investigate for planarity, find the chromatic number and the chromatic index of the graphs

?