This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 3

2011 Philippine MO, 5
Tags: combinatorics , chromatic number
The chromatic number $\chi$ of an (infinite) plane is the smallest number of colors with which we can color the points on the plane in such a way that no two points of the same color are one unit apart. Prove that $4 \leq \chi \leq 7$.

2019 239 Open Mathematical Olympiad, 8
Tags: graph theory , chromatic number , cycle , combinatorics
Given a natural number $k> 1$. Prove that if through any edge of the graph $G$ passes less than $[e(k-1)! - 1]$ simple cycles, then the vertices of this graph can be colored with $k$ colors in the correct way.

Kvant 2024, M2780
Tags: combinatorics , graph theory , chromatic number
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{}$ of $G{}$ such that $\chi(G_1)+\chi(G_2)\geqslant n+1.$ [i]Proposed by V. Dolnikov[/i]