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.
Problem
Source: 2017 China TST 5 P6
Tags: graph theory, combinatorics
14.04.2017 18:14
The last sentence can be: the girth of the graph is not less then 2017 or the shortest cycle in the graph is having a length at least 2017
09.05.2020 18:34
sengeki-niju wrote: 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. Where is $k$ used in this definition of $k-flowing-chromatic$?
09.05.2020 20:30
Does anyone have a solution to this?
18.09.2021 05:16
hard problem
01.06.2022 19:21
I think $k$ is the number of colors of the chess pieces. I think the hamiltonian cycles I choose can be distinct or same. I will work on this problem soon. Can an admin please change the problem statement to clarify the problem?
01.10.2022 06:49
Very intimidating problem, here's an elegant and beautiful solution. The case $ m=1$ is trivial. When $ m=2$, $G$ is a bipartite graph, therefore $\chi(G)$ is either $-1$ or $2$, depending on whether $G$ has a Hamilton cycle. Thus $m \leq 2$ fails. Now we present a way to construct a graph $G$ for any positive integer $C$ with the following properties: 1.$\chi (G)=3$, 2.$G$ has a unique Hamilton cycle, and 3.$ T (G) \ge C$ This is actully not that difficult. We start by picking a sufficiently large integer $N$, the we construct a cycle $C_N$ with $N$ vertices. Label the vertices counterclockwise $u_1,u_2 \cdots u_N$. Define an integer sequence: $$x_1=1, x_{t+1}=x_t +2018+t, 1\leq t \leq D-1$$where $D$ is a sufficient large integer (Note that we need $N$ to be larger than $x_D$). Now connect edges $u_{x_i}u_{x_{i+1}}, 1\leq i \leq D-1$, it is not hard to check that the properties we stated earlier stand when we pick $D\ge 10000C$. Hence our work here is done!