En matemáticas , la coloración de bordes de listas es un tipo de coloración de gráficos que combina coloración de listas y coloración de bordes . Una instancia de un problema de coloración de bordes de lista consiste en un gráfico junto con una lista de colores permitidos para cada borde. Una lista de colores de bordes 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 gráfico G se puede elegir con k -borde si cada instancia de color de borde de lista que tiene G como su gráfico subyacente y que proporciona al menos k colores permitidos para cada borde de G tiene un color adecuado. La posibilidad de elegir el 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, de modo que G es k seleccionable por el borde. Se conjetura que siempre es igual al índice cromático .
Propiedades
Algunas propiedades de ch ′ ( G ):
- ch ′ ( G ) <2 χ ′ ( G ).
- ch ′ (K n , n ) = n . Ésta es la conjetura de Dinitz , probada por Galvin (1995) .
- ch ′ ( G ) <(1 + o (1)) χ ′ ( G ), es decir, el índice cromático de la lista y el índice cromático concuerdan asintóticamente ( Kahn 2000 ).
Aquí χ ′ ( G ) es el índice cromático de G ; y K n , n , el gráfico bipartito completo con conjuntos de partes iguales .
Lista de conjetura para colorear
El problema abierto más famoso sobre la coloración de los bordes de la lista es probablemente la conjetura de la coloración de la lista .
- ch ′ ( G ) = χ ′ ( G ).
Esta conjetura tiene un origen difuso; Jensen y Toft (1995) resumen su historia. La conjetura de Dinitz, probada por Galvin (1995) , es el caso especial de la conjetura de coloración de listas para los gráficos bipartitos completos K n , n .
Referencias
- Galvin, Fred (1995), "The list chromatic index of a bipartite multigraph", 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, págs. 201-202, ISBN 0-471-02865-7.
- Kahn, Jeff (2000), "Asymptotics of the list cromatic index for multigraphs", Random Structures & Algorithms , 17 (2): 117-156, doi : 10.1002 / 1098-2418 (200009) 17: 2 <117 :: AID -RSA3> 3.0.CO; 2-9