MathDB

Chromatic number is countable

Source: Mikl&oacute;s Schweitzer 2018 P1

November 10, 2018

college contestscountability

Problem Statement

Let

S\subset \mathbb{R}

be a closed set and

f:\mathbb{R}^{2n}\to \mathbb{R}

be a continuous function. Define a graph

G

as follows: Let

x

be a vertex of

G

iff

x\in \mathbb{R}^{n}

and

f(x,x)\not\in S

, then connect the vertices

x

and

y

by an edge in

G

iff

f(x,y)\in S

or

f(y,x)\in S

. Show that the chromatic number of

G

is countable.

Back to Problems View on AoPS