Let $k \geq 0$ . Let $G$ be a graph such that every subgraph $H$ contains an independent set of size $\geq (n - k) /2$ , where $n$ is the number of vertices of $H$ . Must $G$ have chromatic number at most $k + 2$ ?

Worked, still open.

graph theory · solved · 0 attempts

use this record

vela registry pull vfr_37aec80d874a0239

vela reproduce examples/erdos-problems

links

solved