Coloración de bordes

En teoría de grafos , una coloración adecuada de los bordes de un grafo es una asignación de "colores" a los bordes del grafo de modo que no haya dos bordes incidentes que tengan el mismo color. Por ejemplo, la figura de la derecha muestra una coloración de los bordes de un grafo con los colores rojo, azul y verde. Las coloraciones de los bordes son uno de los distintos tipos de coloración de grafos . El problema de coloración de los bordes pregunta si es posible colorear los bordes de un grafo dado utilizando como máximo $k$ colores diferentes, para un valor dado de $k$ , o con la menor cantidad posible de colores. El número mínimo requerido de colores para los bordes de un grafo dado se denomina índice cromático del grafo. Por ejemplo, los bordes del grafo de la ilustración se pueden colorear con tres colores, pero no con dos, por lo que el grafo que se muestra tiene un índice cromático de tres.

Según el teorema de Vizing , el número de colores necesarios para colorear los bordes de un grafo simple es su grado máximo $Δ$ o $Δ+1$ . Para algunos grafos, como los grafos bipartitos y los grafos planares de alto grado , el número de colores siempre es $Δ$ , y para los multigrafos , el número de colores puede ser tan grande como $3Δ/2$ . Existen algoritmos de tiempo polinomial que construyen coloraciones óptimas de grafos bipartitos y coloraciones de grafos simples no bipartitos que utilizan como máximo $Δ+1$ colores; sin embargo, el problema general de encontrar una coloración óptima de los bordes es NP-hard y los algoritmos más rápidos conocidos para ello toman un tiempo exponencial. Se han estudiado muchas variaciones del problema de coloración de los bordes, en las que las asignaciones de colores a los bordes deben satisfacer otras condiciones además de la no adyacencia. Las coloraciones de los bordes tienen aplicaciones en problemas de programación y en la asignación de frecuencia para redes de fibra óptica .

Ejemplos

Un gráfico de ciclo puede tener sus bordes coloreados con dos colores si la longitud del ciclo es par: simplemente alterne los dos colores alrededor del ciclo. Sin embargo, si la longitud es impar, se necesitan tres colores. ^[1]

Construcción geométrica de una coloración de 7 aristas del grafo completo $K 8$ . Cada una de las siete clases de color tiene una arista desde el centro hasta el vértice de un polígono y tres aristas perpendiculares a él.

Un grafo completo $K n$ con $n$ vértices es coloreable en sus aristas 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 de $(n - 1)$ lados. Para cada clase de color, incluya una arista desde el centro hasta uno de los vértices del polígono y todas las aristas 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$ aristas, una fracción $1/ n$ del total. ^[2]

Varios autores han estudiado las coloraciones de los bordes de los grafos impares , grafos $n$ -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 como "odd man out" para arbitrar el juego). El caso en el que $n = 3$ da el conocido grafo de Petersen . Como Biggs (1972) explica el problema (para $n = 6$ ), los jugadores desean encontrar un calendario para estos emparejamientos de modo que cada equipo juegue cada uno de sus seis partidos en diferentes días de la semana, con domingos libres para todos los equipos; es decir, formalizando el problema matemáticamente, desean encontrar una coloración de 6 bordes del grafo impar 6-regular $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 , una coloración de borde de un grafo, 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. Una coloración de borde de un grafo $G$ también puede considerarse equivalente a una coloración de vértice del grafo lineal $L (G)$ , el grafo que tiene un vértice para cada borde de $G$ y un borde para cada par de bordes adyacentes en $G$ .

Una coloración de arista adecuada con $k$ colores diferentes se llama una coloración de arista $k$ (adecuada) . Un grafo al que se le puede asignar una coloración de arista $k$ se dice que es $k$ -coloreable en aristas. El número más pequeño de colores necesarios en una coloración de arista (adecuada) de un grafo $G$ es el índice cromático , o número cromático de arista, $χ'(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 las aristas son objetos unidimensionales. Un grafo es $k$ -cromático de arista si su índice cromático es exactamente $k$ . El índice cromático no debe confundirse con el número cromático $χ(G)$ o $χ 0 (G)$ , el número mínimo de colores necesarios en una coloración de vértice adecuada de $G$ .

A menos que se indique lo contrario, se supone que todos los grafos son simples, a diferencia de los multigrafos en los que dos o más aristas pueden conectar el mismo par de puntos finales y en los que puede haber bucles propios. En muchos problemas de coloración de aristas, los grafos simples se comportan de manera diferente a los multigrafos, y se necesita un cuidado adicional para extender los teoremas sobre coloración de aristas de grafos simples al caso de los multigrafos.

Relación con la coincidencia

Este grafo plano regular de 3 elementos tiene 16 vértices y 24 aristas, pero solo 7 aristas en cualquier coincidencia máxima. Por lo tanto, requiere cuatro colores en cualquier coloración de aristas.

Una coincidencia en un grafo $G$ es un conjunto de aristas, de las cuales ninguna es adyacente a otra; una coincidencia perfecta es una coincidencia que incluye aristas que tocan todos los vértices del grafo, y una coincidencia máxima es una coincidencia que incluye tantas aristas como sea posible. En una coloración de aristas, el conjunto de aristas con un color cualquiera debe ser no adyacente entre sí, de modo que formen una coincidencia. Es decir, una coloración de aristas adecuada es lo mismo que una partición del grafo en coincidencias disjuntas.

Si el tamaño de una coincidencia máxima en un grafo dado es pequeño, entonces se necesitarán muchas coincidencias para cubrir todos los bordes del grafo. Expresado de manera más formal, este razonamiento implica que si un grafo tiene $m$ bordes en total, y si como máximo $β$ bordes pueden pertenecer a una coincidencia máxima, entonces cada coloración de borde del grafo debe usar al menos $m /β$ colores diferentes. ^[4] Por ejemplo, el grafo planar de 16 vértices que se muestra en la ilustración tiene $m = 24$ bordes. En este grafo, no puede haber una coincidencia perfecta; porque, si se coincide el vértice central, los vértices no coincidentes restantes se pueden agrupar en tres componentes conectados diferentes con cuatro, cinco y cinco vértices, y los componentes con un número impar de vértices no se pueden coincidir perfectamente. Sin embargo, el grafo tiene coincidencias máximas con siete bordes, por lo que $β = 7.$ Por lo tanto, el número de colores necesarios para colorear los bordes del grafo es al menos 24/7, y dado que el número de colores debe ser un entero, es al menos cuatro.

Para un grafo regular de grado $k$ que no tiene un emparejamiento perfecto, este límite inferior se puede utilizar para mostrar que se necesitan al menos $k + 1 colores.$ ^[4] En particular, esto es cierto para un grafo regular con un número impar de vértices (como los grafos completos impares); para tales grafos, por el lema de apretón de manos , $k$ debe ser par. Sin embargo, la desigualdad $χ' \geq m /β$ no explica completamente el índice cromático de cada grafo regular, porque hay grafos regulares que sí tienen emparejamientos perfectos pero que no son coloreables por k aristas. Por ejemplo, el grafo de Petersen es regular, con $m = 15$ y con $β = 5$ aristas en sus emparejamientos perfectos, pero no tiene una coloración de 3 aristas.

Relación con el grado

Teorema de Vizing

El número cromático de las aristas de un grafo $G$ está muy relacionado con el grado máximo $Δ(G)$ , el mayor número de aristas incidentes en cualquier vértice de $G$ . Claramente, $χ'(G) \geq Δ(G)$ , ya que si $Δ$ aristas diferentes se encuentran todas en el mismo vértice $v$ , entonces a todas estas aristas se les deben asignar colores diferentes entre sí, y eso solo puede ser posible si hay al menos $Δ$ colores disponibles para asignar. El teorema de Vizing (nombrado así por Vadim G. Vizing, quien lo publicó en 1964) establece que este límite es casi estricto: para cualquier grafo, el número cromático de las aristas 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.

Todo 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 los grafos planares de grado máximo de al menos ocho son de clase uno y conjeturó que lo mismo es cierto para los grafos planares de grado máximo siete o seis. Por otra parte, existen grafos planares de grado máximo que van desde dos hasta cinco que son de clase dos. La conjetura ha sido probada desde entonces para grafos de grado máximo siete. ^[8] Los grafos cúbicos planares sin puente son todos de clase 1; esta es una forma equivalente del teorema de los cuatro colores . ^[9]

Gráficas regulares

Una factorización 1 de un grafo k - regular , una partición de las aristas del grafo en correspondencias perfectas , es lo mismo que una coloración k -de las aristas del grafo. Es decir, un grafo regular tiene una factorización 1 si y solo si es de clase 1. Como caso especial de esto, una coloración de 3 aristas de un grafo cúbico (3-regular) a veces se denomina coloración de Tait .

No todos los grafos regulares tienen una factorización 1; por ejemplo, el grafo de Petersen no la tiene. En términos más generales, los snarks se definen como los grafos que, como el grafo de Petersen, no tienen puentes, son 3-regulares y de clase 2.

Según el teorema de König (1916), todo grafo regular bipartito tiene una factorización 1. El teorema fue enunciado anteriormente en términos de configuraciones proyectivas y fue demostrado por Ernst Steinitz .

Multigrafos

Un multigrafo de Shannon con grado seis y multiplicidad de aristas tres, que requiere nueve colores en cualquier coloración de aristas.

Para multigrafos , en los que múltiples aristas paralelas pueden conectar los mismos dos vértices, se conocen resultados similares pero más débiles que el teorema de Vizing que relacionan el número cromático de aristas $χ'(G)$ , el grado máximo $Δ(G)$ , y la multiplicidad $μ(G)$ , el número máximo de aristas en cualquier fibrado de aristas paralelas. Como ejemplo simple que muestra que el teorema de Vizing no se generaliza a multigrafos, considere un multigrafo de Shannon , un multigrafo con tres vértices y tres fibrados de $μ(G)$ aristas paralelas que conectan cada uno de los tres pares de vértices. En este ejemplo, $Δ(G) = 2μ(G)$ (cada vértice es incidente a solo dos de los tres haces de $μ(G)$ aristas paralelas) pero el número cromático de la arista es $3μ(G)$ (hay $3μ(G)$ aristas en total, y cada dos aristas son adyacentes, por lo que a todas las aristas se les deben asignar colores diferentes entre sí). En un resultado que inspiró a Vizing, ^[10] Shannon (1949) mostró que este es el peor caso: $χ'(G) \leq (3/2)Δ(G)$ para cualquier multigrafo $G$ . Además, para cualquier multigrafo $G$ , $χ'(G) \leq Δ(G) + μ(G)$ , una desigualdad que se reduce al teorema de Vizing en el caso de grafos simples (para los cuales $μ(G) = 1$ ).

Algoritmos

Dado que el problema de comprobar si un grafo es de clase 1 es NP-completo , no se conoce ningún algoritmo de tiempo polinomial para colorear los bordes de cada grafo con una cantidad óptima de colores. Sin embargo, se han desarrollado varios algoritmos que flexibilizan uno o más de estos criterios: solo funcionan en un subconjunto de grafos, o no siempre utilizan una cantidad óptima de colores, o no siempre se ejecutan en tiempo polinomial.

Colorear de forma óptima clases especiales de gráficos

En el caso de grafos bipartitos o multigrafos con grado máximo $Δ$ , el número óptimo de colores es exactamente $Δ$ . Cole, Ost y Schirra (2001) demostraron que se puede encontrar una coloración óptima de los bordes de estos grafos en el límite de tiempo casi lineal $O(m log Δ)$ , donde $m$ es el número de bordes en el grafo; 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 grafo de entrada sea regular, sin aumentar su grado ni 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 bordes 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 grafo, lo que hace que el grado se vuelva par. Finalmente, Alon aplica una observación de Gabow (1976), que al seleccionar subconjuntos alternos de aristas en un recorrido de Euler del grafo lo divide en dos subgrafos regulares, para dividir el problema de coloración de las aristas en dos subproblemas más pequeños, y su algoritmo resuelve los dos subproblemas de manera recursiva . El tiempo total para su algoritmo es $O(m log m)$ .

Para los grafos planos con un grado máximo $Δ \geq 7$ , el número óptimo de colores es nuevamente exactamente $Δ$ . Con el supuesto más fuerte de que $Δ \geq 9$ , es posible encontrar una coloración óptima de los bordes en tiempo lineal (Cole & Kowalik 2008).

Para los 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 2020).

Algoritmos que utilizan más de la cantidad óptima de colores

Misra y Gries (1992) y Gabow et al. (1985) describen algoritmos de tiempo polinomial para colorear cualquier gráfico con $Δ + 1$ colores, cumpliendo el límite dado por el teorema de Vizing; consulte el algoritmo de coloración de bordes de Misra y Gries .

Para multigrafos, Karloff y Shmoys (1987) presentan el siguiente algoritmo, que atribuyen a Eli Upfal . Hacer que el multigrafo de entrada $G$ sea euleriano añadiendo un nuevo vértice conectado por una arista a cada vértice de grado impar, encontrar un recorrido de Euler y elegir una orientación para el recorrido. Formar un grafo bipartito $H$ en el que haya dos copias de cada vértice de $G$ , una en cada lado de la bipartición, con una arista 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 tenga una arista desde $u$ hasta $v$ en $G$ . Aplicar un algoritmo de coloración de aristas de grafo bipartito a $H$ . Cada clase de color en $H$ corresponde a un conjunto de aristas en $G$ que forman un subgrafo con grado máximo dos; es decir, una unión disjunta de caminos y 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 grafo bipartito, $O(m log Δ)$ usando el algoritmo de Cole, Ost y Schirra (2001). El número de colores que usa este algoritmo es como máximo , cercano pero no exactamente igual al 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 multigrafos de grado máximo 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 que el grafo sea euleriano, encuentra un recorrido de Euler y luego elige conjuntos alternos de aristas en el recorrido para dividir el grafo en dos subgrafos de grado máximo dos. Los caminos y ciclos pares de cada subgrafo pueden colorearse con dos colores por subgrafo. Después de este paso, cada ciclo impar restante contiene al menos una arista que puede colorearse con uno de los dos colores que pertenecen al subgrafo opuesto. Al eliminar este borde del ciclo impar, queda una ruta, que se puede colorear utilizando los dos colores para su subgráfico. $3\left\lceil {\frac {\Delta }{2}}\right\rceil$ $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$

Un algoritmo de coloración voraz que considera los bordes de un gráfico o multigráfico uno por uno, asignando a cada borde el primer color disponible, puede a veces utilizar hasta $2Δ - 1$ colores, que pueden ser casi el doble de la cantidad de colores necesarios. Sin embargo, tiene la ventaja de que puede usarse en el entorno de algoritmo en línea en el que el gráfico de entrada no se conoce de antemano; en este entorno, su relación competitiva es dos, y esto es óptimo: ningún otro algoritmo en línea 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 fraccionario de cualquier multigrafo (un número que puede calcularse en tiempo polinomial utilizando programación lineal ) está dentro de uno del índice cromático. ^[13] Si estas conjeturas son verdaderas, sería posible calcular un número que nunca esté más de uno fuera del índice cromático en el caso del multigrafo, coincidiendo con lo que se sabe a través del teorema de Vizing para grafos simples. Aunque no se ha demostrado en general, se sabe que estas conjeturas son válidas cuando el índice cromático es al menos , como puede suceder para multigrafos con una multiplicidad suficientemente grande. ^[14] $\Delta +{\sqrt {\Delta /2}}$

Algoritmos exactos

Es sencillo probar si un grafo puede ser coloreado con uno o dos colores en sus aristas, por lo que el primer caso no trivial de coloración de aristas es probar si un grafo tiene una coloración de 3 aristas. Como mostró Kowalik (2009), es posible probar si un grafo tiene una coloración de 3 aristas en un 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 asignaciones posibles de colores a las aristas. Cada grafo 3-regular biconectado con $n$ vértices tiene $O(2 n /2)$ 3-coloraciones de aristas; todas las cuales se pueden enumerar en un tiempo $O(2 n /2)$ (algo más lento que el tiempo para encontrar una sola coloración); Como observó Greg Kuperberg , el gráfico de un prisma sobre un polígono de $n /2 lados tiene coloraciones$ $Ω(2 n /2)$ (límite inferior en lugar de límite superior), lo que demuestra que este límite es estricto. ^[15]

Aplicando algoritmos exactos para la coloración de vértices al gráfico lineal del gráfico de entrada, es posible colorear de manera óptima los bordes de cualquier gráfico con $m$ bordes, independientemente del número de colores necesarios, en tiempo $2 m m O(1)$ y espacio exponencial, o en tiempo $O(2,2461 m)$ y solo espacio polinomial (Björklund, Husfeldt y Koivisto 2009).

Debido a que la coloración de los bordes es NP-completa incluso para tres colores, es poco probable que sea manejable con parámetros fijos cuando se parametriza por el número de colores. Sin embargo, es manejable para otros parámetros. En particular, Zhou, Nakano y Nishizeki (1996) demostraron que para grafos de ancho de árbol $w$ , se puede calcular una coloración de bordes óptima en tiempo $O(nw (6 w) w (w + 1)/2)$ , un límite que depende superexponencialmente de $w$ pero solo linealmente del número $n$ de vértices en el grafo.

Nemhauser y Park (1991) formularon el problema de coloración de bordes como un programa de números enteros y describieron su experiencia con un solucionador de programación de números enteros para colorear los bordes de los gráficos. Sin embargo, no realizaron ningún análisis de complejidad de su algoritmo.

Propiedades adicionales

Un grafo es unívocamente coloreable en $sus k$ aristas si solo hay una manera de dividir las aristas en $k$ clases de color, ignorando las $k!$ posibles permutaciones de los colores. Para $k \neq 3$ , los únicos grafos unívocamente coloreables en $sus k aristas son paths, cycles y$ stars , pero para $k = 3$ otros grafos también pueden ser unívocamente coloreables $en sus k$ aristas. Cada grafo unívocamente coloreable en sus 3 aristas tiene exactamente tres ciclos hamiltonianos (formados al eliminar una de las tres clases de color) pero existen grafos 3-regulares que tienen tres ciclos hamiltonianos y no son unívocamente coloreables en sus 3 aristas, como los grafos de Petersen generalizados $G (6 n + 3, 2)$ para $n \geq 2$ . El único grafo no plano unívocamente coloreable en sus 3 aristas conocido es el grafo de Petersen generalizado $G (9,2)$ , y se ha conjeturado que no existen otros. ^[16]

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 de aristas apropiada de un grafo dado $G$ con $m 1$ aristas 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$ puede transformarse 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 coloraciones de aristas, comenzando desde una coloración que realiza $P$ , cada uno de estos mismos pasos puede realizarse intercambiando los colores $i$ y $j$ en una cadena de Kempe , un camino máximo de aristas que alternan entre los dos colores. En particular, cualquier gráfico tiene una coloración de bordes equitativa , una coloración de bordes 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 utilizarse para transferir muchas propiedades de coloración de aristas de grafos finitos a grafos infinitos . Por ejemplo, los teoremas de Shannon y Vizing que relacionan el grado de un grafo con su índice cromático se generalizan directamente a grafos 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 en el dibujo tienen una de tres pendientes diferentes y que no hay dos aristas que se encuentren en la misma línea una sobre la otra. Si existe tal dibujo, entonces claramente las pendientes de las aristas pueden usarse como colores en una coloración de 3 aristas del gráfico. Por ejemplo, el dibujo del gráfico de utilidad $K 3,3$ como las aristas y las diagonales largas de un hexágono regular representa una coloración de 3 aristas del gráfico de esta manera. Como muestra Richter, un gráfico bipartito simple 3-regular, con una coloración de Tait dada, tiene un dibujo de este tipo que representa la coloración dada si y solo si el gráfico es 3-conexo por aristas . Para un grafo no bipartito, la condición es un poco más complicada: una coloración dada puede representarse mediante un dibujo si la doble cubierta bipartita del grafo está conectada por 3 aristas y si la eliminación de cualquier par monocromático de aristas conduce a un subgrafo que sigue siendo no bipartito. Todas estas condiciones pueden probarse fácilmente en tiempo polinomial; sin embargo, el problema de probar si un grafo 4-regular de 4 aristas coloreadas tiene un dibujo con aristas de cuatro pendientes, que representan los colores por pendientes, es completo para la teoría existencial de los números reales , una clase de complejidad al menos tan difícil como ser NP-completo.

Además de estar relacionado con el grado máximo y el número máximo de coincidencias de un grafo, el índice cromático está estrechamente relacionado con la arboricidad lineal $la(G)$ de un grafo $G$ , el número mínimo de bosques lineales (uniones disjuntas de caminos) en los que se pueden dividir las aristas del grafo. Una coincidencia es un tipo especial de bosque lineal y, en la otra dirección, cualquier bosque lineal puede tener 2 aristas coloreadas, por lo que para cada $G$ se deduce que $la(G) \leq χ'(G) \leq 2 la(G)$ . La conjetura de Akiyama (nombrada por Jin Akiyama ) establece que , de lo que se seguiría con mayor fuerza que $2 la($ $G$ $) - 2 \leq χ'($ $G$ $) \leq 2 la($ $G$ $)$ . Para gráficos de grado máximo tres, $la($ $G$ $)$ es siempre exactamente dos, por lo que en este caso el límite $χ'($ $G$ $) \leq 2 la($ $G$ $)$ coincide con el límite dado por el teorema de Vizing. ^[18] $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$

Otros tipos

El número de Thue de un gráfico es la cantidad de colores necesarios para una coloración de bordes que cumpla con el requisito más estricto de que, en cada ruta de longitud par, la primera y la segunda mitad de la ruta formen secuencias de colores diferentes.

La arboricidad de un grafo es el número mínimo de colores necesarios 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 grafo. ^[19] A diferencia del índice cromático, la arboricidad de un grafo se puede calcular en tiempo polinomial. ^[20]

La coloración de aristas de listas es un problema en el que se da un grafo en el que cada arista está asociada a una lista de colores, y se debe encontrar una coloración de aristas adecuada en la que el color de cada arista se extraiga de la lista de esa arista. El índice cromático de lista de un grafo $G$ es el número $k$ más pequeño con la propiedad de que, sin importar cómo se elijan las listas de colores para las aristas, siempre que cada arista tenga al menos $k$ colores en su lista, se garantiza que será posible una coloración. Por lo tanto, el índice cromático de lista siempre es al menos tan grande como el índice cromático. La conjetura de Dinitz sobre la completitud de cuadrados latinos parciales puede reformularse como la afirmación de que el número cromático de arista de lista del grafo bipartito completo $K n,n$ es igual a su número cromático de arista, $n$ . Galvin (1995) resolvió la conjetura demostrando, de manera más general, que en cada grafo 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 se cumple, incluso de manera más general, para multigrafos arbitrarios sin bucles propios; esta conjetura permanece abierta.

Muchas otras variaciones de coloración de vértices estudiadas comúnmente también se han extendido a coloraciones de aristas. Por ejemplo, la coloración de aristas completa es la variante de coloración de aristas de la coloración completa , una coloración de aristas adecuada en la que cada par de colores debe estar representado por al menos un par de aristas adyacentes y en la que el objetivo es maximizar el número total de colores. ^[21] La coloración de aristas fuerte es la variante de coloración de aristas de la coloración fuerte , una coloración de aristas en la que cada dos aristas con puntos finales adyacentes deben tener colores diferentes. ^[22] La coloración de aristas fuerte tiene aplicaciones en esquemas de asignación de canales para redes inalámbricas . ^[23]

La coloración de aristas acíclica es la variante de coloración de aristas de la coloración acíclica , una coloración de aristas 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 grafo , denotado por , es el número más pequeño de colores necesarios para tener una coloración de aristas acíclica adecuada de . Se ha conjeturado que , donde es el grado máximo de . ^[25] Actualmente, el límite mejor conocido es . ^[26] El problema se vuelve más fácil cuando tiene una circunferencia grande . Más específicamente, existe una constante tal que si la circunferencia de es al menos , entonces . ^[27] Un resultado similar es que para todos existe un tal que si tiene una circunferencia al menos , entonces . ^[28] $G$ $a'(G)$ $G$ $a'(G)\leq \Delta +2$ $\Delta$ $G$ $a'(G)\leq \lceil 3.74(\Delta -1)\rceil$ $G$ $c$ $G$ $c\Delta \log \Delta$ $a'(G)\leq \Delta +2$ $\epsilon >0$ $g$ $G$ $g$ $a'(G)\leq (1+\epsilon )\Delta$

Eppstein (2013) estudió coloraciones de grafos cúbicos con tres aristas, con la propiedad adicional de que no hay dos ciclos bicromáticos que compartan más de una arista entre sí. Demostró que la existencia de tal coloración es equivalente a la existencia de un dibujo del grafo en una cuadrícula de números enteros tridimensional, con aristas paralelas a los ejes de coordenadas y cada línea paralela a los ejes que contiene como máximo dos vértices. Sin embargo, al igual que el problema estándar de coloración de tres aristas, 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, al requerir que tanto los vértices como las aristas estén coloreados. 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. Se ha conjeturado (combinando el teorema de Vizing y el teorema de Brooks ) que cualquier grafo 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 sigue sin demostrarse.

Si un grafo 3-regular sobre una superficie tiene 3 aristas coloreadas, su grafo dual forma una triangulación de la superficie que también tiene aristas coloreadas (aunque, en general, no propiamente coloreadas) de tal manera que cada triángulo tiene una arista de cada color. Se pueden usar otras coloraciones y orientaciones de triangulaciones, con otras restricciones locales sobre cómo se disponen 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 encuentran en cada vértice) se pueden describir combinatoriamente mediante un "etiquetado regular", una coloración dual de las aristas de una triangulación a la subdivisión, con la restricción de que las aristas incidentes a cada vértice formen 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 propia subdivisión rectangular en la que las aristas verticales tienen un color y las aristas horizontales tienen el otro color. También se pueden utilizar restricciones locales similares sobre el orden en que pueden aparecer los bordes coloreados alrededor de un vértice para codificar incrustaciones en cuadrículas de líneas rectas de grafos planares y poliedros tridimensionales con lados paralelos a los ejes. Para cada uno de estos tres tipos de etiquetados regulares, el conjunto de etiquetados regulares de un grafo fijo forma una red distributiva que se puede utilizar para enumerar rápidamente todas las estructuras geométricas basadas en el mismo grafo (como todos los poliedros paralelos a los 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$ d de tal manera que cada dos aristas con el mismo vértice de origen tienen colores distintos. El problema de coloración de carreteras es el problema de colorear las aristas de un grafo dirigido con grados de salida uniformes, de tal manera que el autómata resultante tenga una palabra de sincronización . Trahtman (2009) resolvió el problema de coloración de carreteras al demostrar que dicha coloración se puede encontrar siempre que el grafo dado esté fuertemente conectado y sea aperiódico .

El teorema de Ramsey se ocupa del problema de $k$ -colorear las aristas de un grafo completo grande $K n$ para evitar la creación de subgrafos completos monocromáticos $K s$ de un tamaño dado $s$ . Según el teorema, existe un número $R k (s)$ tal que, siempre que $n \geq R (s)$ , dicha coloración no es posible. Por ejemplo, $R 2 (3) = 6$ , es decir, si las aristas del grafo $K 6$ son 2-coloreadas, siempre habrá un triángulo monocromático.

Se dice que un camino en un grafo con aristas coloreadas es un camino arcoíris si no se repite ningún color en él. Se dice que un grafo tiene colores arcoíris si hay un camino arcoíris entre dos pares de vértices cualesquiera. Una coloración de las aristas de un grafo G con colores 1. . . t es una coloración de intervalo t si se utilizan todos los colores y los colores de las aristas incidentes a cada vértice de G son distintos y forman un intervalo de números enteros.

Aplicaciones

Las coloraciones de los bordes de gráficos completos se pueden utilizar para programar un torneo de todos contra todos en la menor cantidad de rondas posible de modo que cada par de competidores juegue 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 de los bordes 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 todos contra todos; por ejemplo, en la Liga Nacional de Fútbol , los pares de equipos que jugarán entre sí en un año determinado se determinan, en función de 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, independientemente del conjunto de emparejamientos elegido (siempre que ningún equipo juegue entre sí dos veces en la misma temporada), siempre es posible encontrar un calendario que utilice como máximo un fin de semana más que juegos por equipo.

La programación de taller abierto 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 máquina específica, impidiendo 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 coloración de aristas de un multigrafo bipartito, en el que los vértices de un lado de la bipartición representan los objetos a fabricar, los vértices del otro lado de la bipartición representan las máquinas de fabricación, las aristas 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 aristas bipartita puede realizarse 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 redes de acceso múltiple por división de tiempo en redes de sensores como una variante de la coloración de bordes. En este problema, uno debe 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. El uso de una coloración de bordes fuerte (y el uso de dos intervalos de tiempo para cada color de borde, uno para cada dirección) resolvería el problema, pero podría utilizar más intervalos de tiempo de los necesarios. En cambio, buscan una coloración del grafo 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 $v$ y de los vecinos de $v$ . Proponen una heurística para este problema basada en un algoritmo distribuido para la coloración de bordes $(Δ + 1)$ junto con una fase de posprocesamiento que reprograma los bordes que podrían interferir entre sí.

En las comunicaciones por fibra óptica , el problema de coloración de rutas 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 por fibra óptica para cada par, sujeto a la restricción de que no haya dos rutas que compartan un segmento de fibra que utilicen la misma frecuencia entre sí. Las rutas que pasan por el mismo conmutador de comunicaciones pero no por ningún segmento de fibra pueden utilizar la misma frecuencia. Cuando la red de comunicaciones está organizada como una red en estrella , con un único conmutador central conectado por fibras separadas a cada uno de los nodos, el problema de coloración de rutas puede modelarse exactamente como un problema de coloración de bordes de un gráfico o multigráfico, en el que los nodos que se comunican forman los vértices del gráfico, los pares de nodos que desean comunicarse forman los bordes del gráfico y las frecuencias que se pueden utilizar para cada par forman los colores del problema de coloración de 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 pueden unirse para formar una única solución global. ^[33]

Problemas abiertos

Jensen y Toft (1995) enumeran 23 problemas abiertos relacionados con la coloración de aristas, entre los que se incluyen:

La conjetura de Goldberg (1973) de que el índice cromático y el índice fraccionario están dentro uno del otro, lo que permitiría aproximarse al índice cromático dentro de un color en tiempo polinomial.
Varias conjeturas de Jakobsen y otros sobre la estructura de los grafos críticos para la coloración de aristas, grafos de clase 2 tales que cualquier subgrafo tiene un grado máximo menor o es de clase 1. Jakobsen originalmente conjeturó que todos los grafos críticos tienen un número impar de vértices, pero esto fue refutado eventualmente. Varias otras conjeturas que debilitan esta, o que limitan el número de vértices de grafos críticos y multigrafos críticos, permanecen abiertas.
Problema de Vizing de clasificar los grados máximos posibles para los gráficos planares de clase 2.
La conjetura del subgrafo sobrelleno de AJW Hilton, que establece que los grafos con un grado de al menos $n /3$ son de clase 1 o contienen un subgrafo con el mismo grado $Δ$ que el grafo original, y con un número impar $k$ de vértices, de modo que el número de aristas en el subgrafo es mayor que $Δ(k - 1)/2$ , y una conjetura similar de Herbert Grötzsch y Paul Seymour sobre grafos planares en lugar de grafos de alto grado.
Una conjetura de Amanda Chetwynd y Anthony Hilton (que posiblemente se remonta al trabajo de Gabriel Andrew Dirac ) de que los gráficos regulares con un número par $n$ de vértices y con un grado de al menos $n /2$ son de clase 1.
Una conjetura de Claude Berge y DR Fulkerson de que los multigrafos 6-regulares formados al duplicar cada arista de un grafo simple 3-regular sin puente pueden tener los bordes coloreados con seis colores.
Una conjetura de Fiorini y Wilson de que todo grafo planar libre de triángulos , excepto la garra K _1,3 , no es únicamente coloreable en sus 3 aristas .
Una conjetura de 2012 que sostiene que si $G$ es un multigrafo plano $d -regular, entonces$ $G$ es $d$ -coloreable por aristas si y solo si $G$ es $d$ -conexo por aristas de manera impar. 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 8-regular tiene un número cromático de aristas de 8. ^[34]

Notas

^ Soifer (2008), problema 16.4, pág. 133.
^ Soifer (2008), problema 16.5, pág. 133. El hecho de que se necesiten $n$ o $(n - 1) colores es un ejemplo del$ teorema de Vizing .
^ Biggs (1972); Meredith y Lloyd (1973); Biggs (1979).
^ desde Soifer (2008), pág. 134.
^ Rey (1916)
^ Erdős y Wilson (1977).
^ Más sagrado (1981).
^ Sanders y Zhao (2001).
^ Tait (1880); Appel y Haken (1976).
^ Soifer (2008), pág. 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 Peroche (1982); Horak 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 otros (2006).
^ Alon, Sudakov y Zaks (2001); Muthu, Narayanan y Subramanian (2007).
^ Fiamčik (1978); Alon, Sudakov y Zaks (2001)
^ Giotis y otros (2015).
^ Alon, Sudakov y Zaks (2001).
^ Cai y otros (2014).
^ Eppstein (2010).
^ Burke, De Werra y Kingston (2004).
^ Skiena (2008).
^ Williamson y otros (1997).
^ Erlebach y Jansen (2001).
^ Chudnovsky, Edwards y Seymour (2015).

Referencias

Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), "Recubrimiento y empaquetamiento en grafos. III. Invariantes cíclicos y acíclicos", Mathematica Slovaca , 30 (4): 405–417, MR 0595302.
Alon, Noga (2003), "Un algoritmo simple para colorear los bordes de multigrafos bipartitos", Information Processing Letters , 85 (6): 301–302, doi :10.1016/S0020-0190(02)00446-5, MR 1956451, S2CID 34965604.
Alon, Noga ; Sudakov, Benny; Zaks, Ayal (2001), "Coloración acíclica de aristas de grafos", Journal of Graph Theory , 37 (3): 157–167, doi :10.1002/jgt.1010, MR 1837021.
Andersen, Lars Døvling (1977), "Sobre la coloración de los bordes de los grafos", Mathematica Scandinavica , 40 (2): 161–175, doi : 10.7146/math.scand.a-11685 , MR 0465922Como lo citan Chen, Yu y Zang (2011).
Appel, K. ; Haken, W. (1976), "Cada mapa planar es coloreable en cuatro colores", Boletín de la Sociedad Matemática Americana , 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 aristas de grafos en línea competitivo 1.43 en el modelo de llegada de orden aleatorio", Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '10), Society for Industrial and Applied Mathematics, págs. 31–39, ISBN 9780898716986.
Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992), "El algoritmo greedy es óptimo para la coloración de 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), "Coloración de bordes fuerte para la asignación de canales en redes de radio inalámbricas", Proc. Cuarto taller anual de la Conferencia internacional IEEE sobre informática generalizada y comunicaciones (talleres PerCom 2006) , pág. 106, doi :10.1109/PERCOMW.2006.129, ISBN 0-7695-2520-2, Número de identificación del sujeto 5797236.
Biggs, Norman (1972), Guy, Richard K. (ed.), "Un problema de coloración de aristas", Problemas de investigación, American Mathematical Monthly , 79 (9): 1018–1020, doi :10.2307/2318076, JSTOR 2318076.
Biggs, Norman (1979), "Algunas teorías de grafos extrañas", Segunda Conferencia Internacional sobre Matemática Combinatoria, Anales de la Academia de Ciencias de Nueva York , 319 (1): 71–81, Bibcode :1979NYASA.319...71B, doi :10.1111/j.1749-6632.1979.tb32775.x, S2CID 84995087.
Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), "Establecer partición 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 grafos finitos e infinitos", Revista matemática checoslovaca , 22 (97): 272–290, doi : 10.21136/CMJ.1972.101098 , MR 0309777.
Bosák, Juraj; Nešetřil, Jaroslav (1976), "Coloraciones completas y pseudocompletas de un gráfico", Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, SEÑOR 0439672.
Cai, XS; Perarnau, G.; Reed, BA ; Watts, AB (2014), "Coloración de aristas acíclicas de gráficos con gran circunferencia", Random Structures & Algorithms , 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.), Handbook of Graph Theory , CRC Press, pág. 462, ISBN 978-1-58488-090-5.
Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), "Aproximación del índice cromático de multigrafos", 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 (noviembre de 2015), "Coloración de aristas de grafos planos de ocho regularidades", Journal of Combinatorial Theory , Serie B, 115 : 303–338, arXiv : 1209.1176 , doi : 10.1016/j.jctb.2015.05.002.
Cole, Richard; Hopcroft, John (1982), "Sobre la coloración de bordes de gráficos bipartitos", 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 la coloración de aristas de gráficos planares", Algorithmica , 50 (3): 351–368, doi :10.1007/s00453-007-9044-3, MR 2366985, S2CID 7692895.
Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), "Coloración de bordes de multigrafos bipartitos en tiempo $O(E log D)$ ", Combinatorica , 21 (1): 5–12, doi :10.1007/s004930170002, MR 1805711, S2CID 522145.
Cranston, Daniel W. (2006), "Coloración fuerte de los bordes de gráficos con un grado máximo de 4 utilizando 22 colores", Discrete Mathematics , 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), "La complejidad del dibujo de gráficos ortogonales tridimensionales sin curvaturas", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv : 0709.4087 , doi :10.7155/jgaa.00283, S2CID 2716392.
Eppstein, David (2010), "Etiquetas regulares y estructuras geométricas", Proc. 22nd Canadian Conference on Computational Geometry (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 grafos" (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 rutas y la programación de llamadas", Theoretical Computer Science , 255 (1–2): 33–50, doi : 10.1016/S0304-3975(99)00152-8 , MR 1819065.
Ferber, Asaf; Jain, Vishesh (septiembre de 2020), "1-factorizaciones de grafos pseudoaleatorios", Random Structures & Algorithms , 57 (2): 259–278, arXiv : 1803.10361 , doi :10.1002/rsa.20927, S2CID 4680445.
Fiamčik, J. (1978), "La clase cromática acíclica de un grafo", Math. Slovaca , 28 : 139–145.
Fiorini, S.; Wilson, Robin James (1977), Coloración de los bordes de los gráficos , Research Notes in Mathematics, vol. 16, Londres: Pitman, ISBN 0-273-01129-4, Sr. 0543798.
Folkman, Jon ; Fulkerson, DR (1969), "Coloración de aristas en gráficos bipartitos", Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, págs. 561–577, MR 0262112.
Fouquet, J.-L.; Jolivet, J.-L. (1983), "Coloración fuerte de los bordes de los gráficos y aplicaciones a los multi- $k$ -gonos", Ars Combinatoria , 16 (A): 141–150, MR 0737086.
Frieze, Alan M. ; Krivelevich, Michael; Sudakov, Benny (2005), "El fuerte índice cromático de 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), "Uso de particiones de Euler para colorear los bordes de multigrafos bipartitos", 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 la coloración de bordes de gráficos , Informe técnico TRECIS-8501, Universidad de Tohoku.
Gabow, Harold N. ; Westermann, Herbert H. (1992), "Bosques, marcos y juegos: algoritmos para sumas matroidales y aplicaciones", Algorithmica , 7 (5–6): 465–497, doi :10.1007/BF01758774, MR 1154585, S2CID 40358357.
Galvin, F. (1995), "El índice cromático de lista de un multigrafo bipartito", 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 bordes distribuida", Proc. 24th INFOCOM , vol. 4, págs. 2492–2501, doi :10.1109/INFCOM.2005.1498534, ISBN 0-7803-8968-9, Número de identificación del sujeto 8085139.
Giotis, I.; Kirousis, L.; Psaromiligkos, KI; Thilikos, DM (2015), "Sobre el lema local de Lovász algorítmico y la coloración de aristas acíclica", Actas del Duodécimo Taller sobre Algoritmia Analítica y Combinatoria (ANALCO) , pág. 16, doi : 10.1137/1.9781611973761.2 , ISBN 978-1-61197-376-1.
Goldberg, MK (1973), "Multigrafos con un índice cromático casi máximo", Diskret. Analiz. (23): 3–7, 72, MR 0354429Como lo citan Chen, Yu y Zang (2011).
Habib, M.; Péroche, B. (1982), "Algunos problemas sobre arboricidad lineal", Discrete Mathematics , 41 (2): 219–220, doi : 10.1016/0012-365X(82)90209-6 , MR 0676882.
Holyer, Ian (1981), "La NP-completitud de la coloración de aristas", SIAM Journal on Computing , 10 (4): 718–720, doi :10.1137/0210055, S2CID 13131049.
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), Problemas de coloración de gráficos , 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/127635 , S2CID 64, archivado 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", Theoretical Computer Science , 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 fuerte", Discrete Applied Mathematics , 118 (3): 239–248, doi : 10.1016/S0166-218X(01)00237-2 , MR 1892971.
Meredith, Guy HJ; Lloyd, E. Keith (1973), "Los futbolistas de 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 coloración de aristas acíclicas", Discrete Mathematics , 307 (23): 3063–3069, doi : 10.1016/j.disc.2007.03.006 , MR 2371078.
Nash-Williams, C. St. JA (1964), "Descomposición de grafos finitos en bosques", Journal of the London Mathematical Society , Segunda serie, 39 : 12, doi :10.1112/jlms/s1-39.1.12, MR 0161333
Nemhauser, George L. ; Park, Sungsoo (1991), "Un enfoque poliédrico para la coloración de 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 un gráfico coloreable con Tait", en Brandes, Ulrik ; Cornelsen, Sabine (eds.), Proc. 18th International Symposium on Graph Drawing (GD 2010) , Lecture Notes in Computer Science, vol. 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), "Los gráficos planares de grado máximo siete son de clase I", Journal of Combinatorial Theory , Serie B, 83 (2): 201–212, doi : 10.1006/jctb.2001.2047.
Seymour, PD (1979), "Sobre las multicoloridades de los grafos cúbicos y las conjeturas de Fulkerson y Tutte", Actas de la London Mathematical Society , Tercera serie, 38 (3): 423–460, doi :10.1112/plms/s3-38.3.423, MR 0532981.
Schwenk, Allen J. (1989), "Enumeración de ciclos hamiltonianos en ciertos grafos 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 la coloración de las líneas de una red", J. Math. Physics , 28 (1–4): 148–151, doi :10.1002/sapm1949281148, hdl : 10338.dmlcz/101098 , MR 0030203.
Skiena, Steven S. (2008), "16.8 Coloración de bordes", Manual de diseño de algoritmos (2.ª ed.), Springer-Verlag, págs. 548-550, doi :10.1007/978-1-84800-070-4_16, ISBN 978-1-84800-069-8Consulte también el sitio web de esta sección del libro en el Repositorio de algoritmos de Stony Brook.
Soifer, Alexander (2008), El libro para colorear matemático , Springer-Verlag, ISBN 978-0-387-74640-1.
Tait, PG (1880), "Observaciones sobre los colores de los mapas", Proc. R. Soc. Edimburgo , 10 : 729, doi :10.1017/S0370164600044643.
Trahtman, Avraham N. (2009), "El problema de la coloración de las carreteras", 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 p -grafo", Diskret. Analiz. , 3 : 25–30, MR 0180505.
Vizing, VG (1965), "Gráficos críticos con una clase cromática dada", Metody Diskret. Analiz. , 5 : 9–17. (En ruso.)
Williamson, DP ; Hall, Luisiana; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Programas cortos de compras", Investigación de operaciones , 45 (2): 288–294, doi :10.1287/opre.45.2.288, JSTOR 171745, MR 1644998.
Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), "Coloración de bordes de árboles $k$ parciales ", Journal of Algorithms , 21 (3): 598–617, doi :10.1006/jagm.1996.0061, MR 1417666.