Math Problems Vault

Problem 3.1.1

A coloring of a graph (i.e., of the vertices of a graph) in several colors is called proper if the endpoints of every edge are colored in different colors.

Prove that the following three conditions are equivalent:

the graph is bipartite;
the graph can be properly colored with 2 colors;
the graph contains only cycles of even length.

?

Problem 3.1.2

(1)(2)(3)(4)

A coloring of a graph (i.e., of the vertices of a graph) in several colors is called proper if the endpoints of every edge are colored in different colors.

?

(1)

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

(2)

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.

(3)

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.

(4)

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.

Problem 3.1.3

A coloring of a graph (i.e., of the vertices of a graph) in several colors is called proper if the endpoints of every edge are colored in different colors.

If a graph with $n$ vertices contains no $(k+1)$ -anticlique, then the graph cannot be properly colored with fewer than $n/k$ colors.

?

Problem 3.1.4

Several diagonals having no common interior points are drawn in a convex polygon. The resulting plane graph can be properly colored with 3 colors.

?

Problem 3.1.5

(1)(2)(3)

?

(1)

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.

(2)

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.

(3)

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.

Problem 3.1.6

Positive integers $d, k, d_{1}, \ldots , d_{k}$ are such that $d_{1}+d_{2}+\ldots +d_{k} = d+1-k$ . The degree of every vertex of a graph is at most $d$ . Prove that the vertices can be partitioned into $k$ groups so that every vertex of the $i$ -th group is joined to at most $d_{i}$ vertices of its own group.

?

Problem 3.1.7

Three clever girls, Ira, Tanya and Yulia, were each given a copy of the same graph. Yulia and Tanya colored their graphs properly. Yulia used fewer colors than Tanya, but Tanya colored at least two vertices in each color. Prove that Ira can properly color her graph using no more colors than Yulia and so that at least two vertices are colored in each color.

?

Problem 3.1.8

(1)(2)(3)

?

(1)

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.

(2)

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.

(3)

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.

Problem 3.1.9

A directed graph in which at most $d$ edges leave each vertex can be properly colored with $2d+1$ colors.

?

Problem 3.1.10

There are several colors. Each vertex of a bipartite graph with $n \leq 2^{k-1}$ vertices is assigned at least $k$ colors. (The ``lists'' of colors assigned to different vertices may be either the same or different.) Then there exists a proper coloring of the graph that assigns to each vertex some color assigned to it.

?

Problem 3.1.11

(1)(2)

An edge coloring of a graph is called proper if any two edges having a common vertex are colored with different colors.

?

(1)

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.

(2)

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