MathDB

Given positive integers

d \ge 3

r>2

and

l

, with

2d \le l <rd

. Every vertice of the graph

G(V,E)

is assigned to a positive integer in

\{1,2,\cdots,l\}

, such that for any two consecutive vertices in the graph, the integers they are assigned to, respectively, have difference no less than

d

, and no more than

l-d

. A proper coloring of the graph is a coloring of the vertices, such that any two consecutive vertices are not the same color. It's given that there exist a proper subset

A

V

, such that for

G

's any proper coloring with

r-1

colors, and for an arbitrary color

C

, either all numbers in color

C

appear in

A

, or none of the numbers in color

C

appear in

A

. Show that

G

has a proper coloring within

r-1

colors.

Problem Statement