Olimpiada China de Selección de Equipos (TST) 2017 Problema 6
6 Llamamos a un grafo con n vértices $k-flowing-chromatic$ si: 1. podemos colocar una ficha en cada vértice y cualesquiera dos fichas vecinas (conectadas por una arista) tienen colores diferentes. 2. podemos elegir un ciclo hamiltoniano $v_1,v_2,\cdots , v_n$ , y mover la ficha en $v_i$ a $v_{i+1}$ con $i=1,2,\cdots ,n$ y $v_{n+1}=v_1$ , tal que cualesquiera dos fichas vecinas también tienen colores diferentes. 3. después de alguna acción del paso 2 podemos hacer que todas las fichas alcancen cada uno de los n vértices. Sea T(G) el menor número k tal que G es k-flowing-chromatic. Si tal k no existe, denote T(G)=0. Denote $\chi (G)$ el número cromático de G. Halle todos los números positivos m tales que existe un grafo G con $\chi (G)\le m$ y $T(G)\ge 2^m$ sin un ciclo de longitud menor que 2017. sengeki-niju
0
0
Inicia sesión para agregar soluciones y pistas