En teoría de grafos , la coloración de los bordes de un gráfico es una asignación de "colores" a los bordes del gráfico para que no haya dos bordes incidentes del mismo color. Por ejemplo, la figura de la derecha muestra el color del borde de un gráfico con los colores rojo, azul y verde. Los colores de los bordes son uno de los diferentes tipos de colores de gráficos . El problema de colorear los bordes pregunta si es posible colorear los bordes de un gráfico dado usando como máximo k colores diferentes, para un valor dado de k , o con la menor cantidad de colores posibles. El número mínimo requerido de colores para los bordes de un gráfico dado se llama índice cromático.del gráfico. Por ejemplo, los bordes del gráfico en la ilustración se pueden colorear con tres colores pero no con dos colores, por lo que el gráfico que se muestra tiene un índice cromático tres.
Según el teorema de Vizing , el número de colores necesarios para colorear los bordes de un gráfico simple es su grado máximo Δ o Δ + 1 . Para algunos gráficos, como los gráficos bipartitos y los gráficos planos de alto grado , el número de colores es siempre Δ , y para los gráficos múltiples , el número de colores puede ser tan grande como 3Δ / 2 . Existen algoritmos de tiempo polinomial que construyen coloraciones óptimas de gráficos bipartitos y coloraciones de gráficos simples no bipartitos que utilizan como máximo colores Δ + 1 ; sin embargo, el problema general de encontrar una coloración de borde óptima es NP-hard y los algoritmos más rápidos conocidos para ello requieren un tiempo exponencial. Se han estudiado muchas variaciones del problema de la coloración de los bordes, en el que la asignación de colores a los bordes debe satisfacer otras condiciones además de la no adyacencia. Los colores de bordes tienen aplicaciones en problemas de programación y en la asignación de frecuencia para redes de fibra óptica .
Ejemplos de
Un gráfico de ciclo puede tener sus bordes coloreados con dos colores si la duración del ciclo es uniforme: simplemente alterne los dos colores alrededor del ciclo. Sin embargo, si la longitud es impar, se necesitan tres colores. [1]
Un gráfico completo K n con n vértices se puede colorear en los bordes con n - 1 colores cuando n es un número par; este es un caso especial del teorema de Baranyai . Soifer (2008) proporciona la siguiente construcción geométrica de una coloración en este caso: coloque n puntos en los vértices y el centro de un polígono regular ( n - 1) de lados. Para cada clase de color, incluya un borde desde el centro hasta uno de los vértices del polígono y todos los bordes perpendiculares que conectan pares de vértices del polígono. Sin embargo, cuando n es impar, se necesitan n colores: cada color solo se puede usar para ( n - 1) / 2 bordes, una fracción de 1 / n del total. [2]
Varios autores han estudiado los colores de los bordes de los gráficos impares , n gráficos regulares en los que los vértices representan equipos de n - 1 jugadores seleccionados de un grupo de 2 n - 1 jugadores, y en los que los bordes representan posibles emparejamientos de estos equipos (con un jugador quedó como "hombre impar" para arbitrar el juego). El caso de que n = 3 da el conocido gráfico de Petersen . Como Biggs (1972) explica el problema (para n = 6 ), los jugadores desean encontrar un horario para estos emparejamientos de manera que cada equipo juegue cada uno de sus seis juegos en diferentes días de la semana, con los domingos libres para todos los equipos; es decir, al formalizar el problema matemáticamente, desean encontrar una coloración de 6 aristas del gráfico impar de 6 regulares O 6 . Cuando n es 3, 4 u 8, una coloración de borde de O n requiere n + 1 colores, pero cuando es 5, 6 o 7, solo se necesitan n colores. [3]
Definiciones
Al igual que con su contraparte de vértice , la coloración de los bordes de un gráfico, cuando se menciona sin ninguna calificación, siempre se supone que es una coloración adecuada de los bordes, lo que significa que no se asigna el mismo color a dos bordes adyacentes. Aquí, dos bordes distintos se consideran adyacentes cuando comparten un vértice común. Un borde coloración de un gráfico de G también puede ser pensado como equivalente a un vértice coloración de la gráfica de línea L ( G ) , el gráfico que tiene un vértice para cada borde de G y un borde para cada par de bordes adyacentes en G .
Un borde adecuado para colorear con k colores diferentes se llama un (correcto) k -Edge-colorante. Un gráfico al que se le puede asignar un color de borde k se dice que es colorante de borde k . El menor número de colores necesarios en una coloración de borde (adecuada) de un gráfico G es el índice cromático , o número cromático de borde, χ ′ ( G ) . El índice cromático también se escribe a veces usando la notación χ 1 ( G ) ; en esta notación, el subíndice uno indica que los bordes son objetos unidimensionales. Un gráfico es k -edge-cromático si su índice cromático es exactamente k . El índice cromático no se debe confundir con el cromática número χ ( G ) o χ 0 ( G ) , el número mínimo de colores necesarios en un vértice adecuada coloración de G .
A menos que se indique lo contrario, se supone que todos los gráficos son simples, en contraste con los gráficos múltiples en los que dos o más bordes pueden estar conectando el mismo par de puntos finales y en los que puede haber bucles propios. Para muchos problemas de coloración de aristas, los gráficos simples se comportan de manera diferente a los multigrafos, y se necesita un cuidado adicional para extender los teoremas sobre coloraciones de aristas de gráficos simples al caso de multigrafos.
Relación con el emparejamiento
Una coincidencia en un gráfico G es un conjunto de bordes, de los cuales no hay dos adyacentes; una coincidencia perfecta es una coincidencia que incluye bordes que tocan todos los vértices del gráfico, y una coincidencia máxima es una coincidencia que incluye tantos bordes como sea posible. En una coloración de bordes, el conjunto de bordes con cualquier color debe ser no adyacente entre sí, por lo que forman una coincidencia. Es decir, un color de borde adecuado es lo mismo que una partición del gráfico en coincidencias disjuntas.
Si el tamaño de una coincidencia máxima en un gráfico determinado es pequeño, se necesitarán muchas coincidencias para cubrir todos los bordes del gráfico. Expresado de manera más formal, este razonamiento implica que si un gráfico tiene m bordes en total, y si como máximo los bordes β pueden pertenecer a una coincidencia máxima, entonces cada color de borde del gráfico debe usar al menos m / β colores diferentes. [4] Por ejemplo, el gráfico plano de 16 vértices que se muestra en la ilustración tiene m = 24 aristas. En este gráfico, no puede haber una coincidencia perfecta; porque, si el vértice central está emparejado, los vértices no emparejados restantes pueden agruparse en tres componentes conectados diferentes con cuatro, cinco y cinco vértices, y los componentes con un número impar de vértices no pueden emparejarse perfectamente. Sin embargo, el gráfico tiene coincidencias máximas con siete aristas, por lo que β = 7 . Por lo tanto, el número de colores necesarios para colorear los bordes del gráfico es al menos 24 horas al día, 7 días a la semana, y dado que el número de colores debe ser un número entero, es al menos cuatro.
Para una gráfica regular de grado k que no tiene una coincidencia perfecta, este límite inferior se puede usar para mostrar que se necesitan al menos k + 1 colores. [4] En particular, esto es cierto para un gráfico regular con un número impar de vértices (como los gráficos completos impares); para tales gráficos, según el lema del apretón de manos , k debe ser par. Sin embargo, la desigualdad χ ′ ≥ m / β no explica completamente el índice cromático de todos los gráficos regulares, porque hay gráficos regulares que tienen coincidencias perfectas pero que no son k -edge-coloreables. Por ejemplo, el gráfico de Petersen es regular, con m = 15 y con β = 5 aristas en sus combinaciones perfectas, pero no tiene una coloración de 3 aristas.
Relación con el grado
Teorema de Vizing
El número cromática borde de una gráfica G está muy estrechamente relacionado con el grado máximo Δ ( G ) , el mayor número de aristas incidentes a cualquier solo vértice de G . Claramente, χ ′ ( G ) ≥ Δ ( G ) , porque si Δ bordes diferentes se encuentran todos en el mismo vértice v , entonces a todos estos bordes se les debe asignar colores diferentes entre sí, y eso solo puede ser posible si hay al menos Δ colores disponibles para ser asignados. El teorema de Vizing (llamado así por Vadim G. Vizing, quien lo publicó en 1964) establece que este límite es casi estrecho: para cualquier gráfico, el número cromático del borde es Δ ( G ) o Δ ( G ) + 1 . Cuando χ ′ ( G ) = Δ ( G ) , se dice que G es de clase 1; de lo contrario, se dice que es de clase 2.
Cada gráfico bipartito es de clase 1, [5] y casi todos los gráficos aleatorios son de clase 1. [6] Sin embargo, es NP-completo determinar si un gráfico arbitrario es de clase 1. [7]
Vizing (1965) demostró que las gráficas planas de grado máximo al menos ocho son de clase uno y conjeturó que lo mismo es cierto para las gráficas planas de grado máximo siete o seis. Por otro lado, existen grafos planares de grado máximo que van de dos a cinco que son de clase dos. Desde entonces, la conjetura ha sido probada para gráficos de máximo grado siete. [8] Las gráficas cúbicas planas sin puente son todas de clase 1; esta es una forma equivalente del teorema de los cuatro colores . [9]
Gráficos regulares
A 1-factorización de un k - grafo regular , una partición de los bordes de la gráfica en matchings perfectos , es el mismo que un k -Edge de coloración de la gráfica. Es decir, una gráfica regular tiene una factorización 1 si y solo si es de clase 1. Como un caso especial de esto, una coloración de 3 bordes de una gráfica cúbica (3 regular) a veces se denomina coloración Tait .
No todos los gráficos regulares tienen una factorización 1; por ejemplo, el gráfico de Petersen no lo hace. De manera más general, los snarks se definen como los gráficos que, al igual que el gráfico de Petersen, son sin puentes, 3 regulares y de clase 2.
Según el teorema de Kőnig (1916) , cada grafo regular bipartito tiene una factorización 1. El teorema se estableció anteriormente en términos de configuraciones proyectivas y fue probado por Ernst Steinitz .
Multigraphs
Para los gráficos múltiples, en los que múltiples aristas paralelas pueden conectar los mismos dos vértices, se conocen resultados que son similares pero más débiles que el teorema de Vizing relacionando el número cromático de la arista χ ′ ( G ) , el grado máximo Δ ( G ) y la multiplicidad μ ( G ) , el número máximo de aristas en cualquier conjunto de aristas paralelas. Como un ejemplo simple que muestra que el teorema de Vizing no se generaliza a multigraphos, considere un multigraph de Shannon , un multigraph con tres vértices y tres haces de aristas paralelas μ ( G ) que conectan cada uno de los tres pares de vértices. En este ejemplo, Δ ( G ) = 2μ ( G ) (cada vértice incide solo en dos de los tres haces de bordes paralelos μ ( G ) ) pero el número cromático del borde es 3μ ( G ) (hay 3μ ( G) ) bordes en total, y cada dos bordes son adyacentes, por lo que todos los bordes deben tener asignados colores diferentes entre sí). En un resultado que inspiró a Vizing, [10] Shannon (1949) demostró que este es el peor de los casos: χ ′ ( G ) ≤ (3/2) Δ ( G ) para cualquier G multigráfico . Además, para cualquier multigrafo G , χ ′ ( G ) ≤ Δ ( G ) + μ ( G ) , una desigualdad que se reduce al teorema de Vizing en el caso de gráficos simples (para los cuales μ ( G ) = 1 ).
Algoritmos
Debido a que el problema de probar si un gráfico es de clase 1 es NP-completo , no existe un algoritmo de tiempo polinomial conocido para colorear los bordes de cada gráfico con un número óptimo de colores. Sin embargo, se han desarrollado varios algoritmos que relajan uno o más de estos criterios: solo funcionan en un subconjunto de gráficos, o no siempre usan un número óptimo de colores, o no siempre se ejecutan en tiempo polinomial.
Colorear de forma óptima clases especiales de gráficos
En el caso de gráficos bipartitos o multigrafos con grado máximo Δ , el número óptimo de colores es exactamente Δ . Cole, Ost y Schirra (2001) demostraron que una coloración óptima de los bordes de estos gráficos se puede encontrar en el límite de tiempo casi lineal O ( m log Δ) , donde m es el número de bordes en el gráfico; Cole y Hopcroft (1982) y Alon (2003) describen algoritmos más simples, pero algo más lentos . El algoritmo de Alon (2003) comienza haciendo que el gráfico de entrada sea regular, sin aumentar su grado o aumentar significativamente su tamaño, fusionando pares de vértices que pertenecen al mismo lado de la bipartición y luego agregando una pequeña cantidad de vértices y aristas adicionales. . Luego, si el grado es impar, Alon encuentra una única coincidencia perfecta en un tiempo casi lineal, le asigna un color y lo elimina del gráfico, lo que hace que el grado sea par. Finalmente, Alon aplica una observación de Gabow (1976) , que al seleccionar subconjuntos alternos de aristas en un recorrido de Euler del gráfico lo divide en dos subgrafos regulares, para dividir el problema de coloración de aristas en dos subproblemas más pequeños, y su algoritmo resuelve los dos subproblemas. recursivamente . El tiempo total de su algoritmo es O ( m log m ) .
Para gráficos planos con grado máximo Δ ≥ 7 , el número óptimo de colores es nuevamente exactamente Δ . Con la suposición más fuerte de que Δ ≥ 9 , es posible encontrar una coloración de borde óptima en tiempo lineal ( Cole & Kowalik 2008 ).
Para gráficos d-regulares que son pseudoaleatorios en el sentido de que su matriz de adyacencia tiene el segundo valor propio más grande (en valor absoluto) como máximo d 1 − ε , d es el número óptimo de colores ( Ferber y Jain 2018 ).
Algoritmos que utilizan más del número óptimo de colores.
Misra y Gries (1992) y Gabow et al. (1985) describen algoritmos de tiempo polinómico para colorear cualquier gráfico con colores Δ + 1 , cumpliendo con el límite dado por el teorema de Vizing; consulte el algoritmo de coloración de bordes de Misra & Gries .
Para multigrafías, Karloff y Shmoys (1987) presentan el siguiente algoritmo, que atribuyen a Eli Upfal . Haga que el multigrafo de entrada G Euleriano agregue un nuevo vértice conectado por un borde a cada vértice de grado impar, busque un recorrido de Euler y elija una orientación para el recorrido. Forme un gráfico bipartito H en el que haya dos copias de cada vértice de G , una a cada lado de la bipartición, con un borde desde un vértice u en el lado izquierdo de la bipartición hasta un vértice v en el lado derecho de la bipartición. siempre que el recorrido orientado tiene una ventaja de u a v en G . Aplicar un algoritmo del colorante de borde gráfico bipartito a H . Cada clase de color en H corresponde a un conjunto de aristas en G que forman un subgrafo con máximo grado dos; es decir, una unión de la desunión de las trayectorias y de los ciclos, por lo que para cada clase de color en H es posible formar tres clases de color en G . El tiempo para el algoritmo está limitado por el tiempo para colorear los bordes de un gráfico bipartito, O ( m log Δ) utilizando el algoritmo de Cole, Ost & Schirra (2001) . La cantidad de colores que usa este algoritmo es como máximo, cerca pero no exactamente igual que el límite de Shannon de . También se puede convertir en un algoritmo paralelo de una manera sencilla. En el mismo artículo, Karloff y Shmoys también presentan un algoritmo de tiempo lineal para colorear multigrafías de máximo grado tres con cuatro colores (que coinciden con los límites de Shannon y Vizing) que opera con principios similares: su algoritmo agrega un nuevo vértice para hacer el gráfico euleriano, encuentra un recorrido de Euler y luego elige conjuntos alternos de aristas en el recorrido para dividir el gráfico en dos subgráficos de máximo grado dos. Las trayectorias e incluso los ciclos de cada subgrafo se pueden colorear con dos colores por subgrafo. Después de este paso, cada ciclo impar restante contiene al menos un borde que se puede colorear con uno de los dos colores que pertenecen al subgrafo opuesto. Quitar este borde del ciclo impar deja un camino, que puede ser coloreado usando los dos colores para su subgrafo.
Un algoritmo de coloración codicioso que considera los bordes de un gráfico o multigrafo uno por uno, asignando a cada borde el primer color disponible , a veces puede usar hasta 2Δ - 1 colores, que pueden ser casi el doble de la cantidad de colores necesarios. Sin embargo, tiene la ventaja de que se puede utilizar en la configuración del algoritmo en línea en la que el gráfico de entrada no se conoce de antemano; en este escenario, su ratio competitivo es dos, y esto es óptimo: ningún otro algoritmo online puede lograr un mejor rendimiento. [11] Sin embargo, si los bordes llegan en un orden aleatorio, y el gráfico de entrada tiene un grado que es al menos logarítmico, entonces se pueden lograr relaciones competitivas más pequeñas. [12]
Varios autores han hecho conjeturas que implican que el índice cromático fraccional de cualquier multigraph (un número que se puede calcular en tiempo polinomial usando programación lineal ) está dentro de uno de los índices cromáticos. [13] Si estas conjeturas son ciertas, sería posible calcular un número que nunca sea más de uno fuera del índice cromático en el caso de múltiples gráficos, igualando lo que se conoce a través del teorema de Vizing para gráficos simples. Aunque no se ha probado en general, se sabe que estas conjeturas son válidas cuando el índice cromático es al menos, como puede suceder con multigrafos con una multiplicidad suficientemente grande. [14]
Algoritmos exactos
Es sencillo probar si un gráfico puede tener color de borde con uno o dos colores, por lo que el primer caso no trivial de color de borde es probar si un gráfico tiene un color de 3 bordes. Como mostró Kowalik (2009) , es posible probar si una gráfica tiene una coloración de 3 bordes en el tiempo O (1.344 n ) , mientras se usa solo el espacio polinomial. Aunque este límite de tiempo es exponencial, es significativamente más rápido que una búsqueda de fuerza bruta sobre todas las posibles asignaciones de colores a los bordes. Cada biconexas gráfico 3-regular con n vértices tiene O (2 n / 2 ) 3 de borde colorantes; todos los cuales se pueden enumerar en el tiempo O (2 n / 2 ) (algo más lento que el tiempo para encontrar un solo color); como observó Greg Kuperberg , la gráfica de un prisma sobre un polígono de n / 2 lados tiene colores Ω (2 n / 2 ) (límite inferior en lugar de superior), lo que muestra que este límite es estrecho. [15]
Al aplicar algoritmos exactos para colorear vértices al gráfico de líneas del gráfico de entrada, es posible colorear de manera óptima cualquier gráfico con m bordes, independientemente del número de colores necesarios, en el tiempo 2 m m O (1) y espacio exponencial , o en el tiempo O (2.2461 m ) y solo espacio polinomial ( Björklund, Husfeldt & Koivisto 2009 ).
Debido a que la coloración de los bordes es NP-completa incluso para tres colores, es poco probable que sea un parámetro fijo manejable cuando se parametriza por el número de colores. Sin embargo, es manejable para otros parámetros. En particular, Zhou, Nakano y Nishizeki (1996) mostraron que para gráficos de ancho de árbol w , se puede calcular una coloración de borde óptima en el tiempo O ( nw (6 w ) w ( w + 1) / 2 ) , un límite que depende superexponencialmente en w pero solo linealmente en el número n de vértices en el gráfico.
Nemhauser y Park (1991) formulan el problema de coloración de bordes como un programa de números enteros y describen su experiencia usando un solucionador de programación de números enteros para gráficos de color de bordes. Sin embargo, no realizaron ningún análisis de complejidad de su algoritmo.
Propiedades adicionales
Un gráfico es singularmente k -edge-coloreable si solo hay una forma de dividir los bordes en k clases de color, ignorando el k ! posibles permutaciones de los colores. Para k ≠ 3 , las únicas gráficas que se pueden colorear con k -bordes son trayectorias, ciclos y estrellas , pero para k = 3, otras gráficas también pueden ser únicamente con colores con k -bordes. Cada gráfico de color único de 3 bordes tiene exactamente tres ciclos hamiltonianos (formados al eliminar una de las tres clases de color), pero existen gráficos de 3 regulares que tienen tres ciclos de Hamilton y no se pueden colorear de forma única en 3, como los gráficos de Petersen generalizados G (6 n + 3, 2) para n ≥ 2 . El único gráfico no plano conocido con 3 colores únicos es el gráfico de Petersen generalizado G (9,2) , y se ha conjeturado que no existen otros. [dieciséis]
Folkman y Fulkerson (1969) investigaron las secuencias no crecientes de números m 1 , m 2 , m 3 , ... con la propiedad de que existe una coloración adecuada de los bordes de un gráfico G dado con m 1 bordes del primer color, m 2 aristas del segundo color, etc. Observaron que, si una secuencia P es factible en este sentido, y es mayor en orden lexicográfico que una secuencia Q con la misma suma, entonces Q también es factible. Porque, si P > Q en orden lexicográfico, entonces P se puede transformar en Q mediante una secuencia de pasos, cada uno de los cuales reduce uno de los números m i en una unidad y aumenta otro número posterior m j con i < j en una unidad . En términos de colorantes de borde, a partir de una coloración que se da cuenta de P , cada uno de estos mismos pasos se pueden realizar mediante el canje de colores i y j en una cadena Kempe , un camino máxima de bordes que se alternan entre los dos colores. En particular, cualquier gráfico tiene un color de borde equitativo , un color de borde con un número óptimo de colores en el que cada dos clases de color difieren en tamaño como máximo en una unidad.
El teorema de De Bruijn-Erdős puede usarse para transferir muchas propiedades de coloración de bordes de gráficos finitos a gráficos infinitos . Por ejemplo, los teoremas de Shannon y Vizing que relacionan el grado de un gráfico con su índice cromático se generalizan directamente a gráficos infinitos. [17]
Richter (2011) considera el problema de encontrar un dibujo gráfico de un gráfico cúbico dado con las propiedades de que todas las aristas del dibujo tienen una de tres pendientes diferentes y que no hay dos aristas en la misma línea entre sí. Si tal dibujo existe, entonces claramente las pendientes de los bordes pueden usarse como colores en una coloración de 3 bordes del gráfico. Por ejemplo, el dibujo del gráfico de utilidad K 3,3 como los bordes y las diagonales largas de un hexágono regular representa una coloración de 3 bordes del gráfico de esta manera. Como muestra Richter, un gráfico bipartito simple de 3 regulares, con un color Tait dado, tiene un dibujo de este tipo que representa el color dado si y solo si el gráfico está conectado por 3 bordes . Para un gráfico no bipartito, la condición es un poco más complicada: una coloración determinada se puede representar mediante un dibujo si la doble cubierta bipartita del gráfico está conectada a 3 aristas y si la eliminación de cualquier par monocromático de aristas conduce a una subgrafo que todavia no es bipartito. Todas estas condiciones pueden probarse fácilmente en tiempo polinomial; Sin embargo, el problema de probar si un gráfico de 4 colores de 4 bordes tiene un dibujo con bordes de cuatro pendientes, que representan los colores por pendientes, es completo para la teoría existencial de los reales , una clase de complejidad al menos tan difícil como siendo NP-completo.
Además de estar relacionado con el grado máximo y el número máximo de coincidencia de un gráfico, el índice cromático está estrechamente relacionado con la arboricidad lineal la ( G ) de un gráfico G , el número mínimo de bosques lineales (uniones disjuntas de caminos) en el que los bordes del gráfico se pueden dividir. Una coincidencia es un tipo especial de bosque lineal, y en la otra dirección, cualquier bosque lineal puede tener dos colores de borde, por lo que para cada G se sigue que la ( G ) ≤ χ ′ ( G ) ≤ 2 la ( G ) . La conjetura de Akiyama (llamada así por Jin Akiyama ) establece que, de donde se seguiría más fuertemente que 2 la ( G ) - 2 ≤ χ ′ ( G ) ≤ 2 la ( G ) . Para gráficos de máximo grado tres, la ( G ) es siempre exactamente dos, por lo que en este caso el límite χ ′ ( G ) ≤ 2 la ( G ) coincide con el límite dado por el teorema de Vizing. [18]
Otros tipos
El número Thue de un gráfico es el número de colores requeridos en una coloración de borde que cumple con el requisito más estricto de que, en cada trazado de longitud uniforme, la primera y la segunda mitades del trazado forman diferentes secuencias de colores.
La arboricidad de un gráfico es el número mínimo de colores requeridos para que los bordes de cada color no tengan ciclos (en lugar de, en el problema de coloración de bordes estándar, no tener pares de bordes adyacentes). Es decir, es el número mínimo de bosques en los que se pueden dividir los bordes del gráfico. [19] A diferencia del índice cromático, la arboricidad de un gráfico se puede calcular en tiempo polinomial. [20]
La coloración de bordes de lista es un problema en el que se le da a uno un gráfico en el que cada borde está asociado con una lista de colores y debe encontrar un color de borde adecuado en el que el color de cada borde se extrae de la lista de ese borde. El índice cromático de la lista de un gráfico G es el número más pequeño k con la propiedad de que, sin importar cómo se elijan listas de colores para los bordes, siempre que cada borde tenga al menos k colores en su lista, entonces se garantiza un color para ser posible. Por lo tanto, el índice cromático de la lista es siempre al menos tan grande como el índice cromático. La conjetura de Dinitz sobre la finalización de cuadrados latinos parciales puede reformularse como la afirmación de que el número cromático del borde de la lista del gráfico bipartito completo K n, n es igual a su número cromático del borde, n . Galvin (1995) resolvió la conjetura demostrando, de manera más general, que en cada gráfico bipartito el índice cromático y el índice cromático de lista son iguales. Se ha conjeturado que la igualdad entre el índice cromático y el índice cromático de lista es válida, incluso de manera más general, para multigrafías arbitrarias sin bucles propios; esta conjetura permanece abierta.
Muchas otras variaciones comúnmente estudiadas de coloración de vértices también se han extendido a coloraciones de bordes. Por ejemplo, la coloración de bordes completa es la variante de coloración de bordes de la coloración completa , una coloración de bordes adecuada en la que cada par de colores debe estar representado por al menos un par de bordes adyacentes y en el que el objetivo es maximizar el número total de colores. . [21] La coloración de borde fuerte es la variante de coloración de borde de coloración fuerte , una coloración de borde en la que cada dos bordes con extremos adyacentes deben tener colores diferentes. [22] La coloración fuerte de los bordes tiene aplicaciones en los esquemas de asignación de canales para redes inalámbricas . [23]
La coloración de borde acíclica es la variante de coloración de borde de la coloración acíclica , una coloración de borde para la cual cada dos clases de color forman un subgrafo acíclico (es decir, un bosque). [24] El índice cromático acíclico de un gráfico., denotado por , es el menor número de colores necesarios para tener una coloración de borde acíclica adecuada de . Se ha conjeturado que, dónde es el grado máximo de . [25] Actualmente, el límite más conocido es. [26] El problema se vuelve más fácil cuandotiene gran circunferencia . Más específicamente, hay una constante tal que si la circunferencia de Por lo menos , luego . [27] Un resultado similar es que para todos existe un tal que si tiene circunferencia al menos , luego . [28]
Eppstein (2013) estudió la coloración de tres bordes de gráficos cúbicos con la propiedad adicional de que no hay dos ciclos bicromáticos que compartan más de un borde entre sí. Mostró que la existencia de tal coloración es equivalente a la existencia de un dibujo de la gráfica en una cuadrícula de enteros tridimensionales, con bordes paralelos a los ejes de coordenadas y cada línea de eje paralelo conteniendo como máximo dos vértices. Sin embargo, al igual que el problema estándar de coloración de 3 bordes, encontrar una coloración de este tipo es NP-completo.
La coloración total es una forma de coloración que combina la coloración de vértices y aristas, requiriendo que se coloreen tanto los vértices como las aristas. Cualquier par incidente de un vértice y una arista, o una arista y una arista, debe tener colores distintos, al igual que dos vértices adyacentes cualesquiera. Se ha conjeturado (combinando el teorema de Vizing y el teorema de Brooks ) que cualquier gráfico tiene una coloración total en la que el número de colores es como máximo el grado máximo más dos, pero esto no se ha probado.
Si un gráfico de 3 regulares en una superficie tiene 3 colores de borde, su gráfico dual forma una triangulación de la superficie que también tiene el color de borde (aunque, en general, no tiene el mismo color de borde) de tal manera que cada triángulo tiene uno. borde de cada color. Se pueden utilizar otros colores y orientaciones de triangulaciones, con otras restricciones locales sobre cómo se organizan los colores en los vértices o caras de la triangulación, para codificar varios tipos de objetos geométricos. Por ejemplo, las subdivisiones rectangulares (particiones de una subdivisión rectangular en rectángulos más pequeños, con tres rectángulos que se unen en cada vértice) pueden describirse combinatoriamente mediante un "etiquetado regular", una dos coloración de los bordes de una triangulación dual a la subdivisión, con la restricción de que los bordes incidentes a cada vértice forman cuatro subsecuencias contiguas, dentro de cada una de las cuales los colores son los mismos. Este etiquetado es dual a una coloración de la subdivisión rectangular en sí en la que los bordes verticales tienen un color y los bordes horizontales tienen el otro color. También se pueden utilizar restricciones locales similares sobre el orden en el que pueden aparecer los bordes coloreados alrededor de un vértice para codificar incrustaciones de cuadrícula de líneas rectas de gráficos planos y poliedros tridimensionales con lados paralelos al eje. Para cada uno de estos tres tipos de etiquetas regulares, el conjunto de etiquetas regulares de un gráfico fijo forma una red distributiva que se puede usar para enumerar rápidamente todas las estructuras geométricas basadas en el mismo gráfico (como todos los poliedros paralelos de ejes que tienen el mismo esqueleto). ) o para encontrar estructuras que satisfagan restricciones adicionales. [29]
Un autómata finito determinista puede interpretarse como un grafo dirigido en el que cada vértice tiene el mismo grado de salida d , y en el que las aristas están coloreadas en d de tal manera que cada dos aristas con el mismo vértice fuente tienen colores distintos. El problema de colorear la carretera es el problema de colorear los bordes de un gráfico dirigido con grados de salida uniformes, de tal manera que el autómata resultante tenga una palabra sincronizada . Trahtman (2009) resolvió el problema de coloración de carreteras al demostrar que dicha coloración se puede encontrar siempre que el gráfico dado esté fuertemente conectado y sea aperiódico .
El teorema de Ramsey refiere al problema de k -Coloreado los bordes de un gran gráfico completo K n con el fin de evitar la creación de subgrafos completos monocromáticas K s de algún tamaño dado s . Según el teorema, existe un número R k ( s ) tal que, siempre que n ≥ R ( s ) , tal coloración no es posible. Por ejemplo, R 2 (3) = 6 , es decir, si los bordes del gráfico K 6 son de 2 colores, siempre habrá un triángulo monocromático.
Se dice que una ruta en un gráfico de color de borde es una ruta de arco iris si no se repite ningún color en ella. Se dice que una gráfica tiene el color del arco iris si hay una trayectoria de arco iris entre dos pares de vértices. Una coloración de los bordes de un gráfico G con colores 1.. . t es una coloración de intervalo t si se usan todos los colores, y los colores de los bordes incidentes a cada vértice de G son distintos y forman un intervalo de números enteros.
Aplicaciones
Los colores de los bordes de gráficos completos se pueden usar para programar un torneo de todos contra todos en el menor número posible de rondas para que cada par de competidores jueguen entre sí en una de las rondas; en esta aplicación, los vértices del gráfico corresponden a los competidores en el torneo, los bordes corresponden a los juegos y los colores del borde corresponden a las rondas en las que se juegan los juegos. [30] También se pueden utilizar técnicas de coloración similares para programar otros emparejamientos deportivos que no sean para todos; Por ejemplo, en la National Football League , se determinan las parejas de equipos que jugarán entre sí en un año determinado, basándose en los registros de los equipos del año anterior, y luego se aplica un algoritmo de coloración de bordes al gráfico formado por el conjunto de emparejamientos para asignar juegos a los fines de semana en los que se juegan. [31] Para esta aplicación, el teorema de Vizing implica que no importa qué conjunto de emparejamientos se elija (siempre que ningún equipo juegue entre sí dos veces en la misma temporada), siempre es posible encontrar un horario que use como máximo un fin de semana más. que hay juegos por equipo.
La programación de tienda abierta es un problema de programación de procesos de producción , en el que hay un conjunto de objetos a fabricar, cada objeto tiene un conjunto de tareas a realizar en él (en cualquier orden), y cada tarea debe realizarse en una determinada máquina, evitando que cualquier otra tarea que requiera la misma máquina se realice al mismo tiempo. Si todas las tareas tienen la misma longitud, entonces este problema puede formalizarse como uno de colorear los bordes de un multigrafo bipartito, en el que los vértices de un lado de la bipartición representan los objetos que se van a fabricar, los vértices del otro lado de la bipartición representan las máquinas de fabricación, los bordes representan las tareas que deben realizarse y los colores representan los pasos de tiempo en los que se puede realizar cada tarea. Dado que la coloración de bordes bipartita se puede realizar en tiempo polinomial, lo mismo es cierto para este caso restringido de programación de taller abierto. [32]
Gandham, Dawande y Prakash (2005) estudian el problema de la programación de enlaces para protocolos de comunicaciones de red de acceso múltiple por división de tiempo en redes de sensores como una variante de la coloración de los bordes. En este problema, se deben elegir intervalos de tiempo para los bordes de una red de comunicaciones inalámbricas de modo que cada nodo de la red pueda comunicarse con cada nodo vecino sin interferencias. Usar una coloración de borde fuerte (y usar dos ranuras de tiempo para cada color de borde, una para cada dirección) resolvería el problema, pero podría usar más ranuras de tiempo de las necesarias. En cambio, buscan una coloración del gráfico dirigido formado al duplicar cada borde no dirigido de la red, con la propiedad de que cada borde dirigido uv tiene un color diferente de los bordes que salen de vy de los vecinos de v . Proponen una heurística para este problema basada en un algoritmo distribuido para (Δ + 1) -color de borde junto con una fase de posprocesamiento que reprograma los bordes que podrían interferir entre sí.
En la comunicación por fibra óptica , el problema de la coloración de la ruta es el problema de asignar colores (frecuencias de luz) a pares de nodos que desean comunicarse entre sí, y rutas a través de una red de comunicaciones de fibra óptica para cada par, sujeto a la restricción. que no hay dos rutas que compartan un segmento de fibra que usen la misma frecuencia entre sí. Las rutas que pasan por el mismo conmutador de comunicación pero no por ningún segmento de fibra pueden utilizar la misma frecuencia. Cuando la red de comunicaciones está dispuesta como una red en estrella , con un solo conmutador central conectado por fibras separadas a cada uno de los nodos, el problema de coloración de la ruta puede modelarse exactamente como un problema de coloración de borde de un gráfico o multigrafico, en el que los nodos comunicantes forman los vértices del gráfico, los pares de nodos que desean comunicarse forman los bordes del gráfico y las frecuencias que pueden usarse para cada par forman los colores del problema de coloración de los bordes. Para las redes de comunicaciones con una topología de árbol más general, las soluciones de coloración de rutas locales para las redes en estrella definidas por cada conmutador de la red se pueden unir para formar una única solución global. [33]
Problemas abiertos
Jensen y Toft (1995) enumeran 23 problemas abiertos relacionados con la coloración de los bordes. Incluyen:
- La conjetura de Goldberg (1973) de que el índice cromático y el índice fraccionario están dentro de cada uno, lo que permitiría aproximar el índice cromático dentro de un color en tiempo polinomial.
- Varias conjeturas de Jakobsen y otros sobre la estructura de los gráficos críticos para colorear los bordes, gráficos de clase 2 tales que cualquier subgrafo tiene un grado máximo más pequeño o es de clase 1. Jakobsen originalmente conjeturó que todos los gráficos críticos tienen un número impar de vértices, pero esto finalmente fue refutado. Varias otras conjeturas que debilitan esta, o limitan el número de vértices de gráficos críticos y multigrafos críticos, permanecen abiertas.
- El problema de Vizing de clasificar los grados máximos que son posibles para las gráficas planas de clase 2.
- La conjetura del subgrafo sobrecargado de AJW Hilton, que establece que los grafos con grado al menos n / 3 son de clase 1 o contienen un subgrafo con el mismo grado Δ que el grafo original, y con un numero impar k de vrtices, tal que el numero de aristas en el subgrafo es mayor que Δ ( k - 1) / 2 , y una conjetura similar de Herbert Grötzsch y Paul Seymour con respecto a las gráficas planas en lugar de las gráficas de alto grado.
- Una conjetura de Amanda Chetwynd y Anthony Hilton (posiblemente volviendo antes al trabajo de Gabriel Andrew Dirac ) de que las gráficas regulares con un número par n de vértices y con un grado al menos n / 2 son de clase 1.
- Una conjetura de Claude Berge y DR Fulkerson de que los multigrafos de 6 regulares formados al duplicar cada borde de un gráfico simple de 3 regulares sin puentes pueden tener color de borde con seis colores.
- Una conjetura de Fiorini y Wilson de que todo gráfico plano sin triángulos , que no sea la garra K 1,3 , no es únicamente colorable en 3 bordes .
- Una conjetura de 2012 de que si G es un multigraph plano d -regular, entonces G es d -edge-coloreable si y solo si G está extrañamente d -edge-conectado. Esta conjetura es una generalización del teorema de los cuatro colores , que surge en d = 3. Maria Chudnovsky , Katherine Edwards y Paul Seymour demostraron que un multigrafo plano regular de 8 tiene un número cromático de borde de 8. [34]
Notas
- ^ Soifer (2008) , problema 16.4, p. 133.
- ^ Soifer (2008) , problema 16.5, p. 133. El hecho de quese necesiten n o ( n - 1) colores es un ejemplo del teorema de Vizing .
- ^ Biggs (1972) ; Meredith y Lloyd (1973) ; Biggs (1979) .
- ↑ a b Soifer (2008) , p. 134.
- ↑ Kőnig (1916)
- ^ Erdős y Wilson (1977) .
- ^ Holyer (1981) .
- ^ Sanders y Zhao (2001) .
- ↑ Tait (1880) ; Appel y Haken (1976) .
- ^ Soifer (2008) , p. 136.
- ^ Bar-Noy, Motwani y Naor (1992) .
- ^ Bahmani, Mehta y Motwani (2010) .
- ^ Goldberg (1973) ; Andersen (1977) ; Seymour (1979) .
- ^ Chen, Yu y Zang (2011) .
- ^ Eppstein (2013) .
- ^ Schwenk (1989) .
- ^ Bosák (1972) .
- ^ Akiyama, Exoo y Harary (1980) ; Habib y Péroche (1982) ; Horák y Niepel (1982) .
- ^ Nash-Williams (1964) .
- ^ Gabow y Westermann (1992) .
- ^ Bosák y Nešetřil (1976) .
- ^ Fouquet y Jolivet (1983) ; Mahdian (2002) ; Frieze, Krivelevich y Sudakov (2005) ; Cranston (2006) .
- ^ Barrett y col. (2006) .
- ^ Alon, Sudakov y Zaks (2001) ; Muthu, Narayanan y Subramanian (2007) .
- ^ Fiamčik (1978) ; Alon, Sudakov y Zaks (2001)
- ^ Giotis y col. (2015) .
- ^ Alon, Sudakov y Zaks (2001) .
- ^ Cai y col. (2014) .
- ^ Eppstein (2010) .
- ^ Burke, De Werra y Kingston (2004) .
- ^ Skiena (2008) .
- ^ Williamson y col. (1997) .
- ^ Erlebach y Jansen (2001) .
- ^ Chudnovsky, Edwards y Seymour (2012) .
Referencias
- Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), "Cobertura y empaquetado en gráficos. III. Invariantes cíclicos y acíclicos", Mathematica Slovaca , 30 (4): 405–417, MR 0595302.
- Alon, Noga (2003), "Un algoritmo simple para multigraphs bipartitos de coloración de bordes", Information Processing Letters , 85 (6): 301–302, doi : 10.1016 / S0020-0190 (02) 00446-5 , MR 1956451.
- Alon, Noga ; Sudakov, Benny; Zaks, Ayal (2001), "Coloración acíclica de los bordes de los gráficos", Journal of Graph Theory , 37 (3): 157-167, doi : 10.1002 / jgt.1010 , MR 1837021.
- Andersen, Lars Døvling (1977), "Sobre los colores de los bordes de los gráficos", Mathematica Scandinavica , 40 (2): 161-175, doi : 10.7146 / math.scand.a-11685 , MR 0465922. Según lo citado por Chen, Yu y Zang (2011) .
- Appel, K .; Haken, W. (1976), "Cada mapa plano tiene cuatro colores", Boletín de la American Mathematical Society , 82 (5): 711–712, doi : 10.1090 / S0002-9904-1976-14122-5 , MR 0424602.
- Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), "Un algoritmo de coloración de bordes de gráficos en línea competitivo 1.43 en el modelo de llegada de pedidos aleatorios", Actas del 21º Simposio anual ACM-SIAM sobre algoritmos discretos (SODA '10) , págs. 31–39.
- Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992), "El algoritmo codicioso es óptimo para colorear bordes en línea", Information Processing Letters , 44 (5): 251–253, doi : 10.1016 / 0020-0190 (92) 90209-E.
- Barrett, CL; Istrate, G .; Kumar, VSA; Marathe, MV; Thite, S .; Thulasidasan, S. (2006), "Fuerte coloración de los bordes para la asignación de canales en redes de radio inalámbricas", Proc. Cuarta Conferencia Internacional Anual IEEE sobre Talleres de Computación Pervasiva y Comunicaciones (Talleres PerCom 2006) , p. 106, doi : 10.1109 / PERCOMW.2006.129 , ISBN 0-7695-2520-2, S2CID 5797236.
- Biggs, Norman (1972), Guy, Richard K. (ed.), "An edge-coloring problem", Research Problems, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307 / 2318076 , JSTOR 2318076.
- Biggs, Norman (1979), "Alguna teoría de grafos impares", Segunda Conferencia Internacional sobre Matemáticas Combinatorias, Anales de la Academia de Ciencias de Nueva York , 319 (1): 71–81, Código Bibliográfico : 1979NYASA.319 ... 71B , doi : 10.1111 / j.1749-6632.1979.tb32775.x , S2CID 84995087.
- Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), "Establecer particiones mediante inclusión-exclusión" (PDF) , SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137 / 070683933 , MR 2529771.
- Bosák, Juraj (1972), "Índice cromático de gráficos finitos e infinitos", Checoslovaco Mathematical Journal , 22 (97): 272-290, doi : 10.21136 / CMJ.1972.101098 , MR 0309777.
- Bosák, Juraj; Nešetřil, Jaroslav (1976), "Coloración completa y pseudocompleta de un gráfico", Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171-184, MR 0439672.
- Cai, XS; Perarnau, G .; Reed, BA ; Watts, AB (2014), "Coloración de bordes acíclicos de gráficos con circunferencia grande", Estructuras y algoritmos aleatorios , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002 / rsa.20695 , S2CID 7727097.
- Burke, E .; De Werra, D .; Kingston, J. (2004), "5.6.5 Horarios deportivos" , en JL, Gross; Yellen, J. (eds.), Manual de teoría de grafos , CRC Press, p. 462, ISBN 978-1-58488-090-5.
- Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), "Aproximación del índice cromático de multigraphs", Journal of Combinatorial Optimization , 21 (2): 219–246, doi : 10.1007 / s10878-009-9232-y , MR 2770056 , S2CID 169162.
- Chudnovsky, Maria ; Edwards, Katherine; Seymour, Paul (2012), "Grafos planos regulares de ocho colores de bordes", arXiv : 1209.1176 [ cs.DM ].
- Cole, Richard; Hopcroft, John (1982), "On edge coloring bipartite graphs", SIAM Journal on Computing , 11 (3): 540–546, doi : 10.1137 / 0211043 , hdl : 1813/6283 , MR 0664720.
- Cole, Richard; Kowalik, Łukasz (2008), "Nuevos algoritmos de tiempo lineal para gráficos planos de coloración de bordes", Algorithmica , 50 (3): 351–368, doi : 10.1007 / s00453-007-9044-3 , MR 2366985 , S2CID 7692895.
- Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), "Multigraphs bipartite de coloración de bordes en tiempo O ( E log D ) ", Combinatorica , 21 (1): 5–12, doi : 10.1007 / s004930170002 , MR 1805711 , S2CID 522145.
- Cranston, Daniel W. (2006), "Fuerte coloración de bordes de gráficos con grado máximo 4 usando 22 colores", Matemáticas discretas , 306 (21): 2772–2778, arXiv : math / 0601623 , Bibcode : 2006math .... ..1623C , doi : 10.1016 / j.disc.2006.03.053 , MR 2264374 , S2CID 1097275.
- Eppstein, David (2013), "The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155 / jgaa.00283 , S2CID 2716392.
- Eppstein, David (2010), "Etiquetados regulares y estructuras geométricas", Proc. 22a Conferencia Canadiense sobre Geometría Computacional (CCCG 2010) (PDF) , Universidad de Manitoba, arXiv : 1007.0221 , Bibcode : 2010arXiv1007.0221E.
- Erdős, Paul ; Wilson, Robin J. (1977), "Nota sobre el índice cromático de casi todos los gráficos" (PDF) , Journal of Combinatorial Theory , Serie B, 23 (2–3): 255–257, doi : 10.1016 / 0095-8956 (77) 90039-9.
- Erlebach, Thomas; Jansen, Klaus (2001), "La complejidad de la coloración de la ruta y la programación de llamadas", Informática teórica , 255 (1–2): 33–50, doi : 10.1016 / S0304-3975 (99) 00152-8 , MR 1819065.
- Ferber, Asaf; Jain, Vishesh (2018), "1 factorizaciones de gráficos pseudoaleatorios", arXiv : 1803.10361 [ math.CO ].
- Fiamčik, J. (1978), "La clase cromática acíclica de un gráfico", Math. Eslovaca , 28 : 139–145.
- Fiorini, S .; Wilson, Robin James (1977), Coloración de bordes de gráficos , Notas de investigación en matemáticas, 16 , Londres: Pitman, ISBN 0-273-01129-4, MR 0543798.
- Folkman, Jon ; Fulkerson, DR (1969), "Coloración de bordes en gráficos bipartitos", Matemáticas combinatorias y sus aplicaciones (Proc. Conf., Univ. Carolina del Norte, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, págs. 561–577, MR 0262112.
- Fouquet, J.-L .; Jolivet, J.-L. (1983), "Fuerte coloración de bordes de gráficos y aplicaciones a múltiples k - gones", Ars Combinatoria , 16 (A): 141-150, MR 0737086.
- Frieze, Alan M .; Krivelevich, Michael; Sudakov, Benny (2005), "El fuerte índice cromático de los gráficos aleatorios" (PDF) , SIAM Journal on Discrete Mathematics , 19 (3): 719–727 (electrónico), doi : 10.1137 / S0895480104445757 , MR 2191290.
- Gabow, Harold N. (1976), "Using Euler particitions to edge colour bipartite multigraphs", International Journal of Computer and Information Sciences , 5 (4): 345–355, doi : 10.1007 / BF00998632 , MR 0422081 , S2CID 36331285.
- Gabow, Harold N .; Nishizeki, Takao ; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algoritmos para gráficos de coloración de bordes , Tech. Informe TRECIS-8501, Universidad de Tohoku.
- Gabow, Harold N .; Westermann, Herbert H. (1992), "Bosques, marcos y juegos: algoritmos para sumas y aplicaciones de matroides", Algorithmica , 7 (5–6): 465–497, doi : 10.1007 / BF01758774 , MR 1154585 , S2CID 40358357.
- Galvin, F. (1995), "The list chromatic index of a bipartite multigraph", Journal of Combinatorial Theory , Serie B, 63 (1): 153-158, doi : 10.1006 / jctb.1995.1011.
- Gandham, S .; Dawande, M .; Prakash, R. (2005), "Programación de enlaces en redes de sensores: revisión de la coloración de los bordes distribuidos", Proc. 24th INFOCOM , 4 , págs. 2492–2501, doi : 10.1109 / INFCOM.2005.1498534 , ISBN 0-7803-8968-9, S2CID 8085139.
- Giotis, I .; Kirousis, L .; Psaromiligkos, KI; Thilikos, DM (2015), "Sobre el lema local algorítmico de Lovász y la coloración acíclica de los bordes", Actas del Duodécimo Taller de Algoritmia Analítica y Combinatoria (ANALCO) , p. 16, doi : 10.1137 / 1.9781611973761.2 , ISBN 978-1-61197-376-1.
- Goldberg, MK (1973), "Multigraphs con un índice cromático casi máximo", Diskret. Analiz. (23): 3–7, 72, MR 0354429. Según lo citado por Chen, Yu y Zang (2011) .
- Habib, M .; Péroche, B. (1982), "Algunos problemas sobre arboricidad lineal", Matemáticas discretas , 41 (2): 219-220, doi : 10.1016 / 0012-365X (82) 90209-6 , MR 0676882.
- Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing , 10 (4): 718–720, doi : 10.1137 / 0210055.
- Horák, Peter; Niepel, Ľudovít (1982), "Una breve demostración de un teorema de arboricidad lineal para grafos cúbicos", Acta Mathematica Universitatis Comenianae , 40/41: 275-277, MR 0686983.
- Jensen, Tommy R .; Toft, Bjarne (1995), Graph Coloring Problems , Nueva York: Wiley-Interscience, ISBN 0-471-02865-7.
- Karloff, Howard J .; Shmoys, David B. (1987), "Algoritmos paralelos eficientes para problemas de coloración de bordes", Journal of Algorithms , 8 (1): 39–52, doi : 10.1016 / 0196-6774 (87) 90026-5 , MR 0875324.
- König, D. (1916), "Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" , Mathematische Annalen , 77 (4): 453-465, doi : 10.1007 / BF01456961 , hdl : 10338.dmlcz / 127.635 , S2CID 121097364 , archivada del original el 19 de enero de 2015 , consultado el 30 de septiembre de 2013.
- Kowalik, Łukasz (2009), "Coloración de bordes mejorada con tres colores", Ciencias de la computación teóricas , 410 (38–40): 3733–3742, doi : 10.1016 / j.tcs.2009.05.005 , MR 2553326.
- Mahdian, Mohammad (2002), "Sobre la complejidad computacional de la coloración de bordes fuertes", Matemáticas aplicadas discretas , 118 (3): 239–248, doi : 10.1016 / S0166-218X (01) 00237-2 , MR 1892971.
- Meredith, Guy HJ; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory , Serie B, 15 (2): 161-166, doi : 10.1016 / 0095-8956 (73) 90016-6.
- Misra, J .; Gries, David (1992), "Una prueba constructiva del teorema de Vizing", Information Processing Letters , 41 (3): 131-133, doi : 10.1016 / 0020-0190 (92) 90041-S.
- Muthu, Rahul; Narayanan, N .; Subramanian, CR (2007), "Límites mejorados en la coloración de bordes acíclicos", Matemáticas discretas , 307 (23): 3063–3069, doi : 10.1016 / j.disc.2007.03.006 , MR 2371078.
- Nash-Williams, C. St. JA (1964), "La descomposición de grafos finitos en los bosques", Revista de la Sociedad Matemática de Londres , Second Series, 39 : 12, doi : 10.1112 / JLMS / s1-39.1.12 , MR 0161333
- Nemhauser, George L .; Park, Sungsoo (1991), "Un enfoque poliédrico para colorear los bordes", Operations Research Letters , 10 (6): 315–322, doi : 10.1016 / 0167-6377 (91) 90003-8 , MR 1128970.
- Richter, David A. (2011), "Cómo dibujar una gráfica coloreable de Tait", en Brandes, Ulrik; Cornelsen, Sabine (eds.), Proc. 18o Simposio Internacional sobre Dibujo de Gráficos (GD 2010) , Lecture Notes in Computer Science, 6502 , Springer-Verlag, págs. 353–364, doi : 10.1007 / 978-3-642-18469-7_32 , ISBN 978-3-642-18468-0.
- Sanders, Daniel P .; Zhao, Yue (2001), "Las gráficas planas de grado máximo siete son clase I", Journal of Combinatorial Theory , Serie B, 83 (2): 201–212, doi : 10.1006 / jctb.2001.2047.
- Seymour, PD (1979), "Sobre multicolores de gráficas cúbicas y conjeturas de Fulkerson y Tutte", Proceedings of the London Mathematical Society , Third Series, 38 (3): 423-460, doi : 10.1112 / plms / s3-38.3 0.423 , MR 0532981.
- Schwenk, Allen J. (1989), "Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados", Journal of Combinatorial Theory , Serie B, 47 (1): 53-59, doi : 10.1016 / 0095-8956 (89) 90064- 6 , MR 1007713.
- Shannon, Claude E. (1949), "Un teorema sobre colorear las líneas de una red", J. Math. Física , 28 (1–4): 148–151, doi : 10.1002 / sapm1949281148 , hdl : 10338.dmlcz / 101098 , MR 0030203.
- Skiena, Steven S. (2008), "16.8 Edge Coloring", The Algorithm Design Manual (2ª ed.), Springer-Verlag, págs. 548–550, doi : 10.1007 / 978-1-84800-070-4_16 , ISBN 978-1-84800-069-8. Consulte también el sitio web para esta sección del libro en Stony Brook Algorithm Repository.
- Soifer, Alexander (2008), El libro de colorear matemático , Springer-Verlag, ISBN 978-0-387-74640-1.
- Tait, PG (1880), "Observaciones sobre la coloración de mapas", Proc. R. Soc. Edimburgo , 10 : 729, doi : 10.1017 / S0370164600044643.
- Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007 / s11856-009-0062-5 , S2CID 515742.
- Vizing, VG (1964), "Sobre una estimación de la clase cromática de un gráfico p ", Diskret. Analiz. , 3 : 25–30, SR. 0180505.
- Vizing, VG (1965), "Gráficos críticos con determinada clase cromática", Metody Diskret. Analiz. , 5 : 9-17. (En ruso.)
- Williamson, DP ; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Short shop schedule", Operations Research , 45 (2): 288–294, doi : 10.1287 / opre.45.2.288 , JSTOR 171745 , MR 1644998.
- Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), " Árboles k parciales para colorear los bordes", Journal of Algorithms , 21 (3): 598–617, doi : 10.1006 / jagm.1996.0061 , MR 1417666.