Problem

Source: 2017 China TST 5 P6

Tags: graph theory, combinatorics



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$ to $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.