Coloración de vértices de un gráfico$G$ de modo que los colores aparezcan dos veces

Question

1. Deje $G=(V,E)$ ser un grafo cuyos vértices puede ser coloreado con $m$-colores, de tal manera que cada color aparece al menos dos veces.

2. Deje $\lambda(G)$ denotar el mínimo número de colores necesarios para un vértice para colorear de $G$

Uso 1. para probar que el colorante se puede lograr con $\lambda(G)$ colores

Deje $\alpha$ denotar un colorante con la propiedad 1. y $\beta$ para colorear con $\lambda(G)$ colores. $\beta$ tiene un color de clase con sólo un vértice si $\beta$ no tiene la propiedad 1.

No sé cómo eso ayuda a probar que el colorante se puede lograr con $\lambda(G)$ colores

Edit: Un colorante de la gráfica de $G$ es apropiado para colorear. $u,v$ tienen diferentes colores si $(u,v)\in E$

Agradecería cualquier ayuda

Answer 1

Llame a la dada para colorear con al menos dos vértices de cada color un amistoso para colorear.

Ahora a empezar con el colorante que se utiliza el mínimo número de colores. Si cada color se utiliza dos veces hemos terminado. Si no, elige un vértice con un solo color, buscar los vértices con los que comparte su color en el amistoso para colorear y repintar ellos con el solo color. Repetir mientras no están solos vértices.

Está claro que esto siempre da un admisibles para colorear y que no aumenta el número de colores. Pero el procedimiento debe detenerse porque un repintado vértice no va a volver a pintar de nuevo. Así que terminamos con un amistoso mínima para colorear.