Math Problems Vault

Problem 4.5.1

For any graphs $G$ and $H$ there exists a positive integer $x$ such that for any coloring of the edges of the graph $K_x$ in two colors there is either a subgraph of the first color isomorphic to $G$ or a subgraph of the second color isomorphic to $H$ .

The smallest such number $x$ is denoted by $R(G, H)$ .

?

Problem 4.5.2

$R(G, H) \geqslant (\chi (G) - 1)(c(H) - 1) + 1$ , where $\chi (G)$ is the chromatic number of the graph $G$ , and $c(H)$ is the number of vertices in the largest connected component.

?

Problem 4.5.3

(1)(2)

Denote by $T_m$ a tree on $m$ vertices.

?

(1)

$R(T_m, K_n) = (m-1)(n-1) + 1$ .

(2)

If $m - 1$ divides $n - 1$ , then $R(T_m, K_{1,n}) = m + n - 1$ .

Problem 4.5.4

Denote by $nK_3$ the graph consisting of $n$ (vertex-)disjoint triangles.

?

(1)

$R(nK_3, nK_3) \geqslant 5n$ .

(2)

The edges of a complete graph are colored blue and red. If the graph contains a blue triangle and a red triangle, then among the vertices of these triangles there are five vertices $A, B, O, C, D$ such that the triangle $AOB$ is blue and the triangle $COD$ is red.

(3)

$R(nK_3, nK_3) \leqslant 5n + 1$ .

(4)

$R(2K_3, 2K_3) = 10$ .

(5)

$R(nK_3, nK_3) = 5n$ for any $n > 1$ .

Problem 4.5.5

Find $R(K_3, C_n)$ , where $C_n$ is the cycle on $n$ vertices (see Sec. 2.1).

?