MathDB

Consider a natural number

n\geqslant 3

and a graph

G{}

with a chromatic number

\chi(G)=n

which has more than

n{}

vertices. Prove that there exist two vertex-disjoint subgraphs

G_1{}

and

G_2{}

G{}

such that

\chi(G_1)+\chi(G_2)\geqslant n+1.

Proposed by V. Dolnikov

Problem Statement