Olimpiada China TST 5 2017 Problema 6

Llamamos a un grafo con n vértices $k-flowing-chromatic$ si: 1. podemos colocar una pieza de ajedrez en cada vértice y dos piezas de ajedrez vecinas cualesquiera (conectadas por una arista) tienen diferentes colores. 2. podemos elegir un ciclo hamiltoniano $v_1,v_2,\cdots , v_n$ , y mover la pieza de ajedrez en $v_i$ a $v_{i+1}$ con $i=1,2,\cdots ,n$ y $v_{n+1}=v_1$ , de tal manera que dos piezas de ajedrez vecinas cualesquiera también tengan diferentes colores. 3. después de alguna acción del paso 2 podemos hacer que todas las piezas de ajedrez alcancen cada uno de los n vértices. Sea T(G) denote 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. Encuentra todos los números positivos m tales que hay un grafo G con $\chi (G)\le m$ y $T(G)\ge 2^m$ sin un ciclo de longitud menor que 2017.

26

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados