coloración de bordes de lista

En teoría de grafos , la coloración de aristas por lista es un tipo de coloración de grafos que combina la coloración por lista y la coloración de aristas . Un ejemplo de un problema de coloración de aristas por lista consiste en un grafo junto con una lista de colores permitidos para cada arista. Una coloración de aristas por lista consiste en elegir un color para cada arista de su lista de colores permitidos; una coloración es propia si no hay dos aristas adyacentes que reciban el mismo color.

Un grafo G es k -elegible por aristas si cada instancia de coloración de aristas por lista que tiene a G como su grafo subyacente y que proporciona al menos k colores permitidos para cada arista de G tiene una coloración adecuada. En otras palabras, cuando la lista para cada arista tiene longitud k , sin importar qué colores se pongan en cada lista, se puede seleccionar un color de cada lista de manera que G esté correctamente coloreado. La elegabilidad de aristas , o colorabilidad de aristas por lista , número cromático de aristas por lista , o índice cromático de lista , ch'( G ) del grafo G es el menor número k tal que G es k -elegible por aristas. 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 .

Algunas propiedades de ch'( G ) :

1. ${\displaystyle \operatorname {ch} '(G)<2\chi '(G).}$
2. ${\displaystyle \operatorname {ch} '(K_{n,n})=n.}$ Esta es la conjetura de Dinitz , demostrada por Galvin (1995) .
3. ${\displaystyle \operatorname {ch} '(G)<(1+o(1))\chi '(G),}$es decir, el índice cromático de la lista y el índice cromático coinciden asintóticamente ( Kahn 2000 ) .
4. Para grafos bipartitos,${\displaystyle ch'(G)=\chi '(G)}$. ^{[ 1 ]} Para cada grafo bipartito simple ,${\displaystyle ch'(G)=\Delta}$. ^{[ 2 ]}

El problema abierto más famoso sobre la coloración de aristas de listas es probablemente la conjetura de coloración de listas .

$${\displaystyle \operatorname {ch} '(G)=\chi '(G).}$$

Esta conjetura tiene un origen difuso; Jensen y Toft (1995) ofrecen una visión general de 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 .

• Galvin, Fred (1995), "El índice cromático de lista de un multigrafo bipartito", Journal of Combinatorial Theory , Serie B, 63 : 153–158 , doi : 10.1006/jctb.1995.1011.
• Jensen, Tommy R.; Toft, Bjarne (1995), "12.20 List-Edge-Chromatic Numbers", Graph Coloring Problems , Nueva York: Wiley-Interscience, pp. 201–202 , ISBN  0-471-02865-7.
• Kahn, Jeff (2000), "Asintótica del índice cromático de lista para multigrafos", Random Structures & Algorithms , 17 (2): 117–156 , doi : 10.1002/1098-2418(200009)17:2 < 117::AID-RSA3 > 3.0.CO ; 2-9