MathDB

We call a graph with n vertices

k-flowing-chromatic

if: 1. we can place a chess on each vertex and any two neighboring (connected by an edge) chesses have different colors. 2. we can choose a hamilton cycle

v_1,v_2,\cdots , v_n

, and move the chess on

v_i

v_{i+1}

with

i=1,2,\cdots ,n

and

v_{n+1}=v_1

, such that any two neighboring chess also have different colors. 3. after some action of step 2 we can make all the chess reach each of the n vertices. Let T(G) denote the least number k such that G is k-flowing-chromatic. If such k does not exist, denote T(G)=0. denote

\chi (G)

the chromatic number of G. Find all the positive number m such that there is a graph G with

\chi (G)\le m

and

T(G)\ge 2^m

without a cycle of length small than 2017.

Problem Statement