El número c-cromático se define en el papel Particiones de gráficos en cografías . Pide el número mínimo de colores utilizados para colorear los vértices, de modo que cada clase de color sea un cograma . Cograph es un gráfico libre de P4 , es decir, no hay una ruta inducida de longitud 3.
El documento denota el número c-cromático como y demuestra que en el Comentario 12 en la página 4. La prueba se puede utilizar para Convierta cualquier coloración a una coloración como máximo de colores, en tiempo polinómico.
En el estudio de la coloración gráfica clásica, es decir, el número cromático , se discutió la coloración codiciosa . El rendimiento del color codicioso está determinado por el orden de los vértices. En el peor de los casos, un gráfico necesita colores mientras que . Esto implica que la relación de aproximación del color codicioso es arbitrariamente mala.
Del mismo modo, cuando estamos coloreando el gráfico en cografías, podemos usar el color codicioso. Dado un orden de vértices, etiquete cada vértice con el color más pequeño (suponga que los colores están etiquetados como 1, 2, 3, ...) de modo que cada clase de color sea un cograma.
Mi pregunta es:
- ¿Cuál es el peor comportamiento de la coloración codiciosa en la cografía?
- ¿Es posible que la coloración codiciosa necesite más que colores?