Olimpiada China de Selección de Equipos (TST) 2019 Problema 6
6 Dados enteros positivos $d \ge 3$ , $r>2$ y $l$ , con $2d \le l <rd$ . A cada vértice del grafo $G(V,E)$ se le asigna un entero positivo en $\{1,2,\cdots,l\}$ , tal que para cualesquiera dos vértices consecutivos del grafo, los enteros que se les asignan, respectivamente, tienen diferencia no menor que $d$ , y no mayor que $l-d$ . Un coloreo propio del grafo es un coloreo de los vértices, tal que cualesquiera dos vértices consecutivos no tengan el mismo color. Se sabe que existe un subconjunto propio $A$ de $V$ , tal que para cualquier coloreo propio de $G$ con $r-1$ colores, y para un color arbitrario $C$ , o bien todos los números del color $C$ aparecen en $A$ , o bien ninguno de los números del color $C$ aparece en $A$ . Demuestre que $G$ tiene un coloreo propio con $r-1$ colores.
1
0
Inicia sesión para agregar soluciones y pistas