En matemáticas , el coloreado de bordes de listas es un tipo de coloreado de gráficos que combina el coloreado de listas y el coloreado de bordes . Una instancia de un problema de coloración de bordes de lista consta de un gráfico junto con una lista de colores permitidos para cada borde. Una coloración de borde de lista es una elección de un color para cada borde, de su lista de colores permitidos; una coloración es adecuada si no hay dos bordes adyacentes que reciban el mismo color.
Un grafo G es seleccionable por k aristas si cada instancia de lista de colores de aristas que tiene G como su grafica subyacente y que proporciona al menos k colores permitidos para cada arista de G tiene una coloración apropiada. La elegibilidad del borde , o la colorabilidad del borde de la lista, el número cromático del borde de la lista , o el índice cromático de la lista , ch′( G ) del gráfico G es el menor número k tal que G es k -borde seleccionable. Se conjetura que siempre es igual al índice cromático .
Aquí χ′( G ) es el índice cromático de G ; y K n , n , el grafo bipartito completo con conjuntos de partes iguales .
Esta conjetura tiene un origen borroso; Jensen & Toft (1995) resumen su historia. La conjetura de Dinitz, demostrada por Galvin (1995) , es el caso especial de la conjetura de coloración de listas para los grafos bipartitos completos K n , n .