Erdős Problems

Browse all problems

↑ ↓ to move↵ to openesc to close

Loading problem…

Status

On this page

Status

Topics

Terms Privacy info@plasma.ai

Problem 922 — Erdős Problems

Problem 922

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$ ?

Source: erdosproblems.com/922

Graph theory
Chromatic number

Wiki page

Status

Solved·, Proved

An accepted solution exists. The statement is true.

Proved. Folkman [Fo70b] proved the bound (claim page (Folkman, 1970)). The question is from Erdős and Hajnal [ErHa67b], who could settle only the immediate case $k=0$ and not $k=1$ .

ErHa67b: Erdős, P. and Hajnal, András, On chromatic graphs. Mat. Lapok 18 (1967), 1-4.
Fo70b: Folkman, J. H., An upper bound on the chromatic number of a graph. Combinatorial Theory and its Applications, Colloq. Math. Soc. János Bolyai 4 (1970), 437-457.

Proof claims

Loading proof claims…

Discussion

Loading discussion…

PreviousProblem 921 NextProblem 923

On this page

Statement
Status
References
Proof claims
Discussion

Status: Solved, Proved
Topics: Graph theory
Chromatic number
In the wiki: Wiki page