Borde para colorear

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de septiembre de 2022; la verificación requiere 1 edición .

La coloración de bordes es la asignación de "colores" a los bordes de un gráfico de tal manera que no haya dos bordes adyacentes que tengan el mismo color. La coloración de bordes es uno de los diferentes tipos de coloración de gráficos. El problema de coloración de bordes pregunta si es posible colorear los bordes de un gráfico dado con colores diferentes como máximo para un valor dado o para el número mínimo posible de colores. El número mínimo de colores necesarios para colorear los bordes de un gráfico determinado se denomina índice cromático del gráfico. Por ejemplo, los bordes del gráfico de la ilustración se pueden colorear con tres colores, pero no con dos, por lo que el gráfico tiene un índice cromático de 3. $k$ $k$

De acuerdo con el teorema de Vizing , el número de colores necesarios para colorear los bordes de un gráfico simple es igual al grado máximo de vértices , o . Para algunos gráficos, como gráficos bipartitos y gráficos planos de alto grado , la cantidad de colores siempre es , mientras que para multigrafías , la cantidad de colores puede ser de hasta . Hay algoritmos de tiempo polinomial que producen una coloración óptima de gráficos bipartitos y una coloración de un gráfico no bipartito simple con varios colores . Sin embargo, en el caso general, el problema de encontrar el color de línea óptimo es NP-completo , y el algoritmo conocido más rápido se ejecuta en tiempo exponencial. Se han estudiado muchas variantes del problema de coloración de bordes, en las que las condiciones para asignar un color a un borde deben satisfacer otras condiciones además de la conjugación. Los problemas de coloración de bordes tienen aplicaciones en problemas de programación y asignación de frecuencias en redes de fibra óptica . $\Delta$ $\Delta +1$ $\Delta$ $3{\Delta}/2$ ${\Delta}+1$

Ejemplos

El ciclo del gráfico se puede colorear en 2 colores si la duración del ciclo es uniforme; solo use 2 colores a la vez, pasando secuencialmente los bordes del ciclo. Sin embargo, en caso de una longitud impar, se requieren 3 colores [1] .

Los bordes de un gráfico completo con vértices se pueden codificar por colores si son pares. Este es un caso especial del teorema de Baranyai . Soifer [2] da la siguiente construcción geométrica de la coloración en este caso: colocamos puntos en las esquinas y en el centro de un -gon regular. Para cada clase de color, seleccionamos un borde que conecta el centro y uno de los vértices del polígono, y todos los bordes perpendiculares a él, que conectan pares de vértices del polígono. Sin embargo, si se requieren colores impares, cada color solo se puede usar para colorear los bordes, la -ésima parte de todos los bordes [3] . $K_n$ $norte$ $n-1$ $norte$ $norte$ $(n-1)$ $norte$ $norte$ $(n-1)/2$ $1/n$

Algunos autores han estudiado la coloración de los bordes de gráficos impares , gráficos regulares en los que los vértices representan equipos de jugadores de un número total de jugadores, y en los que los bordes representan posibles parejas de estos equipos (con un jugador fuera de juego como árbitro). En el caso donde obtenemos el conocido gráfico de Petersen . Como explica Biggs $norte$ $(n-1)$ $2n-1$ $n=3$ [4] , el problema (para) es que los jugadores quieren encontrar un horario tal que los equipos jueguen cada uno de los seis juegos en diferentes días de la semana, excepto el domingo para todos los jugadores. En la formulación matemática, quieren encontrar una coloración de línea de 6 colores de gráficos de 6 regulares. Cuandoes igual a 3, 4 u 8, la coloración de la línea del gráficorequierecolores, pero para 5, 6 y 7, solocolores [5] . $n=6$ $O_{6}$ $norte$ $En}$ $n+1$ $norte$

Definiciones

Al igual que con la coloración de vértices , la coloración de los bordes de un gráfico, a menos que se indique explícitamente lo contrario, siempre asume que a dos bordes adyacentes se les asignan colores diferentes. Dos aristas se consideran adyacentes si tienen un vértice común. La coloración de los bordes de un gráfico se puede considerar como el equivalente a la coloración de los vértices de un gráfico de líneas , un gráfico que tiene un vértice para cada borde del gráfico y un borde para cada par de bordes adyacentes . $GRAMO$ $L(G)$ $GRAMO$ $GRAMO$

Una coloración adecuada con diferentes colores se denomina coloración de borde (adecuada) . Si se puede encontrar una coloración de borde (adecuada) para un gráfico, se dice que es coloreable de borde . El menor número de colores necesarios para la coloración (correcta) de las líneas de un gráfico se denomina índice cromático o número cromático de borde . El índice cromático a veces se escribe como . En esta notación, el índice indica que los bordes son objetos unidimensionales. Un gráfico tiene color en los bordes si el índice cromático es exactamente . El índice cromático no debe confundirse con el número cromático , o sea , el número mínimo de colores necesarios para colorear adecuadamente los vértices de un gráfico . $k$ $k$ $k$ $k$ $GRAMO$ $\chi {\prime}(G)$ $\ chi _ {1} (G)$ $k$ $k$ $\ chi (G)$ $\chi _{0}(G)$ $GRAMO$

A menos que se indique lo contrario, se supone que todos los gráficos son simples, a diferencia de los multigrafos , en los que dos o más aristas pueden conectar el mismo par de vértices y en los que puede haber bucles (una arista cuyos vértices finales son los mismos). Para la mayoría de los problemas de coloreado de líneas, los gráficos simples se comportan de manera diferente a los multigrafos, y se requiere especial cuidado al extender los teoremas de coloreado de líneas de gráficos simples a multigrafos.

Relación con coincidencias

Una correspondencia en un gráfico es un conjunto de aristas de las cuales dos no son adyacentes. Un emparejamiento se llama perfecto si sus aristas contienen todos los vértices del grafo y máximo si contiene el máximo número posible de aristas. En una coloración de bordes, los bordes del mismo color no deben ser adyacentes, por lo que forman una coincidencia. Por lo tanto, una coloración adecuada de los bordes es lo mismo que descomponer un gráfico en coincidencias disjuntas. $GRAMO$

Si el tamaño de la coincidencia máxima en un gráfico dado es pequeño, se necesita una gran cantidad de coincidencias para cubrir todos los bordes del gráfico. Más formalmente, esta explicación supone que si un gráfico tiene bordes, y si un máximo de bordes puede pertenecer a una coincidencia máxima, entonces cada color de borde del gráfico debe contener al menos colores distintos. [6] Por ejemplo, el gráfico plano de 16 vértices que se muestra en la ilustración tiene bordes. No hay correspondencia perfecta en este gráfico: si el vértice central pertenece a la coincidencia, los vértices restantes se pueden dividir en tres grupos conectados con el número de vértices 4, 5, 5. Los subgráficos resultantes con un número impar de vértices no tener una combinación perfecta. Sin embargo, el gráfico tiene una coincidencia máxima con siete aristas, por lo que . Por lo tanto, la cantidad de colores necesarios para colorear los bordes de un gráfico es al menos 24/7, y dado que la cantidad de colores debe ser un número entero, obtenemos al menos 4 colores. $metro$ $\beta$ $m/\beta$ $metro=24$ $\beta=7$

Para gráficos regulares de grados que no coinciden perfectamente, este límite inferior se puede usar para mostrar que se necesitan al menos colores. [6] En particular, esto es cierto para grafos regulares con un número impar de vértices. Para tales gráficos, según el lema del apretón de manos, , a su vez, debe ser par . Sin embargo, la desigualdad no explica completamente el índice cromático de un gráfico regular arbitrario, ya que hay gráficos regulares que tienen una coincidencia perfecta pero no son k -edge- coloreables. Por ejemplo, el gráfico de Petersen es regular con y con aristas en una combinación perfecta, pero no tiene una coloración de 3 aristas. $k$ $k+1$ $k$ $\chi {\prime}\geqslant m\beta$ $metro=15$ $\beta=5$

Relación con el título

Teorema de Vizing

El número cromático de los bordes de un gráfico está estrechamente relacionado con el grado máximo (el número máximo de bordes adyacentes a cualquier vértice del gráfico ). Está claro que , por lo que si diferentes aristas contienen un vértice , entonces todas estas aristas deben colorearse con diferentes colores, lo cual es posible solo si hay al menos colores. El teorema de Vizing (llamado así por Vadim Vizing , quien lo publicó en 1964) establece que este límite es casi exacto: para cualquier gráfico, el número cromático del borde es , o . Si , se dice que G es de clase 1, en caso contrario se dice que es de clase 2. $GRAMO$ ${\Delta}(G)$ $GRAMO$ $\chi {\prime}(G)\geq {\Delta}(G)$ ${\Delta}$ $v$ $\Delta$ ${\Delta}(G)$ $\Delta (G)+1$ $\chi {\prime}(G)={\Delta}(G)$

Cualquier gráfico bipartito tiene clase 1 [7] y casi todos los gráficos aleatorios tienen clase 1 [8] . Sin embargo, el problema de verificar si un gráfico arbitrario tiene clase 1 es un problema NP-completo [9] .

Vizing [10] probó que los gráficos planos de grado máximo al menos ocho tienen clase 1 y conjeturó que lo mismo es cierto para los gráficos planos de grado 7 o 6. Por otro lado, hay gráficos planos con grado máximo entre dos y cinco que tienen clase 2. Desde entonces, la conjetura ha sido probada para siete [11] . Grafos planares sin puentes Los grafos cúbicos tienen clase 1, y esto es equivalente a la formulación del problema de los cuatro colores [12] .

Gráficos regulares

La factorización en 1 de un gráfico regular k , es decir, la descomposición de los bordes del gráfico en combinaciones perfectas , es lo mismo que la coloración del borde k del gráfico. Por lo tanto, un gráfico regular tiene una factorización de 1 si y solo si tiene clase 1. Un caso especial, la coloración de líneas de 3 colores de gráficos cúbicos (3-regulares) a veces se denomina coloración de Tite .

No todos los gráficos regulares tienen una factorización de 1. Por ejemplo, Graf Petersen no lo hace. Los snarks se definen como gráficos que, al igual que el gráfico de Petersen, no tienen puente, son 3 regulares y de clase 2.

De acuerdo con el teorema de Koenig [7] , cualquier gráfico regular bipartito tiene una factorización de 1. El teorema fue formulado anteriormente en términos de configuraciones proyectivas y probado por Ernst Steinitz .

Multigrafos

Para multigrafos , en los que múltiples aristas pueden conectar los mismos dos vértices, se conocen resultados similares pero más débiles según el teorema de Wizing con respecto al número cromático de aristas , el grado máximo y la multiplicidad , el número máximo de aristas en un paquete de aristas paralelas (es decir, que tienen el mismo picos finales). Como ejemplo simple que muestra que el teorema de Vizing no se generaliza a los multigrafos, considere el multigrafo de Shannon , un multigrafo con tres vértices y tres haces de aristas paralelas que conectan cada par de vértices. En este ejemplo: - cada vértice es adyacente a solo dos de los tres grupos de aristas paralelas, pero el número cromático de la arista es (en el gráfico de aristas, dos aristas cualesquiera son adyacentes, por lo que todas las aristas deben tener colores diferentes). En un artículo inspirado en el teorema de Vizing, Soifer y Shannon [13] [14] demostraron que este es el peor caso para cualquier multigrafo . Además, para cualquier multigrafo . Esta desigualdad se reduce al teorema de Vizing para grafos simples (para ellos ). $\chi {\prime}(G)$ $\Delta (G)$ $\tazón)$ $\tazón)$ $\Delta (G)=2\mu (G)$ $\tazón)$ $3\mu (G)$ $3\mu (G)$ $\chi {\prime}(G)\leq (3/2)\Delta (G)$ $GRAMO$ $GRAMO$ $\chi {\prime}(G)\leq \Delta (G)+\mu (G)$ $\mu (G)=1$

Algoritmos

Dado que el problema de verificar si un gráfico tiene clase 1 es NP-completo , no existe un algoritmo conocido de coloreado de línea de tiempo polinomial para ningún gráfico que proporcione un coloreado óptimo. Sin embargo, se han desarrollado una serie de algoritmos que debilitan uno o más criterios: funcionan en un subconjunto de gráficos, o no siempre dan la cantidad óptima de colores, o no siempre funcionan en tiempo polinomial.

Coloración óptima de algunas 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 . Se demostró en 2001 [15] que el color de línea óptimo de estos gráficos se puede encontrar en un tiempo casi lineal , donde es el número de aristas en el gráfico. Cole y Hopcroft [16] y Alon [17] han descrito previamente algoritmos más simples pero algo más lentos . El algoritmo de Alon comienza haciendo que el gráfico sea regular sin aumentar mucho el grado o el tamaño al fusionar pares de vértices que pertenecen a la misma parte del gráfico bipartito y luego agregar una pequeña cantidad de vértices y aristas. Después de eso, si el grado es impar, Alon encuentra una coincidencia perfecta en tiempo lineal, le asigna un color y lo elimina del gráfico, lo que da como resultado un gráfico de grado par. Finalmente, Alon usa la observación de Gabov [18] de que elegir subconjuntos alternos de bordes en el ciclo de Euler de un gráfico lo divide en dos subgráficos regulares, transformando el problema de coloración de bordes en dos problemas más pequeños, por lo que su algoritmo ahora resuelve estos dos subproblemas recursivamente . El tiempo total de ejecución del algoritmo se estima en . $\Delta$ $\Delta$ $O(m\,\log\Delta)$ $metro$ $O(m\,\log m)$

Para gráficos planos con grado máximo , el número óptimo de colores es nuevamente exactamente . Bajo una suposición más estricta de que , uno puede encontrar el color de borde óptimo en tiempo lineal [19] . ${\Delta}\geq 7$ $\Delta$ ${\Delta}\geq 9$

Algoritmos que utilizan más colores de los necesarios para una coloración óptima

Existen algoritmos de tiempo polinomial para colorear cualquier gráfico con colores, lo que corresponde al límite dado por el teorema de Vizing [20] [21] . $\Delta +1$

Para los multigrafos en 1987 [22] existe el siguiente algoritmo (atribuido a Eli Upfal ): el multigrafo original se hace Euler añadiendo un vértice conectado por aristas a todos los vértices de grado impar; se encuentra el camino de Euler, se elige la orientación para este camino; se crea un grafo bipartito que contiene dos copias de cada vértice del grafo , uno en cada parte, y aristas desde un vértice en la parte izquierda hasta un vértice en la parte derecha, cuando un camino dirigido tiene un arco desde hasta en el gráfico . A continuación, aplicamos el algoritmo de coloreado de bordes de gráfico bipartito para el gráfico . Cada color en corresponde a un conjunto de aristas en , lo que forma un subgrafo con máximo grado dos, es decir, una unión disjunta de caminos y ciclos de modo que por cada color en , se pueden formar tres colores en . El tiempo de ejecución del algoritmo está limitado por el tiempo de colorear un gráfico bipartito utilizando el algoritmo de Cole, Ost y Schirr [15] . El número de colores que utiliza este algoritmo no excede , que está cerca, pero no es lo mismo que, el límite de Shannon . Lo mismo se puede hacer con un algoritmo paralelo directamente. En el mismo artículo, Karloff y Schmois también proponen un algoritmo de tiempo lineal para colorear multigrafías de como máximo tercer grado con cuatro colores (que satisface tanto el límite de Shannon como el límite de Weezing). Este algoritmo funciona con principios similares: el algoritmo también agrega un vértice para hacer que el gráfico sea euleriano, encuentra una ruta de Euler y luego selecciona conjuntos alternos de aristas en la ruta para dividir el gráfico en dos subconjuntos de máximo grado dos. Los caminos e incluso los ciclos de cada subconjunto se pueden colorear en dos colores (dos colores por subgráfico). El siguiente paso es colorear las aristas de los ciclos impares en los que al menos una arista se puede colorear con uno de los dos colores pertenecientes al subgráfico opuesto. Al eliminar este borde del ciclo impar, se deja un camino que se puede colorear con dos colores. $GRAMO$ $H$ $GRAMO$ $tu$ $v$ $tu$ $v$ $GRAMO$ $H$ $H$ $GRAMO$ $H$ $GRAMO$ $O(m\,\log\Delta)$ $3\left\lceil {\frac {\Delta}2}\right\rceil$ $\left\lpiso {\frac {3\Delta}2}\right\rpiso$

Un algoritmo de coloración codicioso que selecciona secuencialmente los bordes de un gráfico o multigráfico y asigna el primer color válido a veces puede usar colores que pueden ser casi el doble del número de colores requerido. Sin embargo, tiene la ventaja de que puede usarse en algoritmos en línea que no saben nada sobre la estructura del gráfico de antemano. Bajo estas condiciones, su coeficiente competitivo es igual a dos, y este coeficiente es óptimo - ningún otro algoritmo puede dar mejores indicadores [23] . Sin embargo, si las aristas llegan en orden aleatorio y el gráfico original tiene al menos un grado logarítmico, se puede obtener un coeficiente competitivo más pequeño [24] . $2{\Delta}-1$

Algunos autores plantearon la hipótesis de que el índice cromático fraccionario de cualquier multigrafo (un número que se puede calcular en tiempo polinomial mediante programación lineal ) difiere del índice cromático en no más de uno [25] . Si la conjetura es correcta, será posible encontrar un número que no difiera en más de uno del índice cromático en el caso de los multigrafos, lo que corresponde al teorema de Vizing para grafos simples. Aunque, en el caso general, la conjetura no ha sido probada, se sabe que es verdadera si el índice cromático no es menor que , tal como en el caso de multigrafos con multiplicidad suficientemente grande [26] . ${\ Delta }+{\ sqrt {{\ Delta }/2))$

Algoritmos exactos

Es fácil verificar si un gráfico se puede colorear con uno o dos colores en los bordes, por lo que el primer caso no trivial de coloreado es verificar si un gráfico se puede colorear con tres colores. En 2009 [27] , se demostró que es posible verificar si hay una coloración de los bordes de un gráfico con tres colores en el tiempo usando solo un espacio polinomial. Aunque estos límites de tiempo son exponenciales, es sustancialmente más rápido que el algoritmo de búsqueda de fuerza bruta al observar todos los colores de borde posibles. Cualquier gráfico de 3 vértices regulares doblemente conectado tiene coloraciones de 3 aristas. Y todos ellos se pueden enumerar en el tiempo (un poco más lento que el tiempo de búsqueda de un color). Como señaló Kuperberg , la gráfica de un prisma sobre un -ágono tiene muchos colores, lo que demuestra que este límite es exacto [28] . $O(1,344^{n})$ $norte$ $O(2^{{n/2}})$ $O(2^{{n/2}})$ $n/2$

Al aplicar algoritmos exactos para colorear los vértices de un gráfico de líneas , se puede colorear de manera óptima cualquier gráfico con bordes, independientemente de la cantidad de colores necesarios, en el tiempo usando el espacio exponencial o en el tiempo y el espacio polinomial [29] . $metro$ $2^{m}m^{{O(1)}}$ $O(2,2461^{m})$

Dado que el problema de coloración de bordes es NP-completo incluso para tres colores, es poco probable que se preste a una parametrización fija por el número de colores. Sin embargo, la tarea se presta a la parametrización por otros parámetros. En particular, Zhou, Nakano y Nishiseki [30] demostraron que para los gráficos de ancho de árbol, el color de línea óptimo se puede encontrar en el tiempo , que crece exponencialmente a partir del número de vértices del gráfico, pero solo linealmente . $w$ $O(nw(6w)^{{w(w+1)/2}})$ $w$ $norte$

En 1991 [31] , el problema de coloración de bordes se formuló como un problema de programación de enteros y se llevaron a cabo experimentos usando paquetes de programación de enteros para colorear los bordes de los gráficos, pero no se proporcionó ningún análisis de la complejidad de dichos algoritmos.

Propiedades adicionales

Un gráfico es coloreable únicamente por los bordes si y solo si hay una sola forma de dividir los bordes en clases de color, sin contar las posibles permutaciones de colores. Para los gráficos, los bordes únicamente pueden colorearse solo son caminos, ciclos y estrellas , pero para otros gráficos pueden ser únicamente los bordes coloreables. Cualquier gráfico coloreable únicamente de 3 bordes tiene exactamente tres ciclos hamiltonianos (formados al eliminar uno de los tres colores), pero hay gráficos de 3 regulares que tienen tres ciclos hamiltonianos pero no tienen una coloración única de 3 bordes, como Gráficos de Petersen generalizados para . Solo se conoce un gráfico no plano coloreable únicamente de 3 aristas, este es el gráfico de Petersen generalizado , y existe la conjetura de que no hay otros [32] . $k$ $k$ $k!$ $k\neq 3$ $k$ $k = 3$ $k$ $G(6n+3,2)$ $n\geq 2$ $G(9,2)$

Folkman y Fulkerson [33] estudiaron secuencias no crecientes de números para los cuales hay una coloración de borde de un gráfico dado con bordes del primer color, bordes del segundo color, y así sucesivamente. Se dieron cuenta de que si una secuencia encaja en el sentido descrito, y si es lexicográficamente mayor que una secuencia con la misma suma, entonces encaja. Si lexicográficamente, se puede convertir a paso a paso, disminuyendo uno de los números en uno en cada paso y aumentando el siguiente número ( ) en uno. En cuanto a la coloración de los bordes, comenzamos con la coloración , luego intercambiamos secuencialmente el color y en la cadena de Kempe , la ruta más larga de bordes alterna dos colores. En particular, cualquier gráfico tiene una coloración de línea justa , una coloración de borde con un número óptimo de colores en el que dos clases de colores difieren en tamaño como máximo en uno. $m_{1},m_{2},m_{3},...$ $GRAMO$ $m_1$ $m_2$ $PAGS$ $q$ $q$ $P>Q$ $PAGS$ $q$ $mi$ $m_{j}$ $yo<j$ $PAGS$ $i$ $j$

El teorema de Bruijn-Erdős se puede utilizar para ampliar muchas propiedades de la coloración de líneas de gráficos finitos a infinitos . Por ejemplo, los teoremas de Shannon y Vizing sobre la relación entre el grado de un gráfico y su índice cromático se generalizan fácilmente a infinitos gráficos [34] .

En 2011 [35] , se consideró el problema de encontrar una imagen de un gráfico cúbico dado con las propiedades de que todos los bordes de la imagen tienen uno de los tres ángulos de inclinación diferentes y que no hay dos bordes en la misma línea. Si existe tal representación del gráfico en la figura, está claro que el ángulo de inclinación de los bordes puede considerarse como el color de los bordes en una coloración tricolor del gráfico. Por ejemplo, el patrón de aristas y diagonales largas de un hexágono regular representa una coloración de 3 aristas de un gráfico de esta manera. Se muestra que un grafo bipartito 3-regular con un coloreado Tite dado tiene una representación gráfica de esta forma si y solo si es k-edge-connected . Para los gráficos no bipartitos, la condición es un poco más complicada: una coloración determinada puede representarse mediante un patrón de este tipo si la cubierta bipartita doble del gráfico está conectada por 3 bordes y si la eliminación de dos bordes del mismo color conduce a un color no bipartito. subgrafo Todas estas condiciones son fáciles de comprobar en tiempo polinomial, sin embargo, el problema de comprobar si un gráfico de 4 colores de 4 aristas tiene un patrón con cuatro pendientes correspondientes a los colores es completo para la teoría de la existencia de los números reales , de la misma clase de complejidad que NP-completitud. $K_{{3,3}}$

Teniendo una conexión con el grado máximo y el número máximo de coincidencias de un gráfico, el índice cromático también está estrechamente relacionado con el treeiness del gráfico , el número mínimo de bosques lineales (unión disjunta de caminos) en los que se encuentran los bordes del gráfico. se puede particionar. La coincidencia es un tipo especial de bosque lineal, pero, por otro lado, cualquier bosque lineal puede tener 2 bordes de color, por lo que para cualquier . La conjetura de Akiyama establece que , lo que implicaría una mayor desigualdad . Para grafos de grado máximo, tres es siempre exactamente igual a dos, por lo que la restricción corresponde a la frontera que sigue del teorema de Vizing [36] . $retraso)$ $GRAMO$ $GRAMO$ $la(G)\leq \chi {\prime}(G)\leq 2la(G)$ ${\mahop {{\mathrm {la}}}}(G)\leq \left\lceil {\frac {{\Delta }+1}{2}}\right\rceil$ $2la(G)-2\leq \chi {\prime }(G)\leq 2la(G)$ $retraso)$ $\chi {\prime}(G)\leq 2la(G)$

Otros tipos de coloración de bordes

El número de Thue del gráfico es el número de colores necesarios para una coloración de borde que satisface un requisito más fuerte que cualquier ruta de longitud uniforme, a saber, que la primera y la segunda mitad de la ruta deben formar diferentes secuencias de colores.

El treeiness de un gráfico es el número mínimo de colores necesarios para colorear de tal manera que los bordes de cualquier color no contengan ciclos (y no, como en el problema de coloreado estándar, los bordes del mismo color no son adyacentes). Por lo tanto, este es el número mínimo de elementos del bosque en el que se pueden descomponer los bordes del gráfico [37] . A diferencia del número cromático, el ancho del bosque se puede calcular en tiempo polinomial [38] .

El problema del coloreado de borde prescrito es un problema en el que, para un gráfico dado, para cada arco del cual se da una lista de colores, es necesario encontrar un coloreado de borde adecuado, en el que cada color se toma de un lista dada. El índice cromático prescrito de un gráfico es el número más pequeñopara el cual, independientemente de la elección de las listas de colores de los bordes, si cada borde recibe al menoscolores, se garantiza que existe una coloración. El índice cromático prescrito no es siempre inferior al número cromático. La conjetura de Dinitz sobre el llenado de cuadrados latinos parcialesse puede reformular como la afirmación de que el número cromático de borde prescrito de un gráfico bipartito completo es igual a su número cromático de borde. En 1995 [39] , se resolvió la conjetura y se demostró una afirmación más fuerte de que para cualquier gráfico bipartito, el índice cromático y el índice cromático prescrito son iguales. Se establece una conjetura aún más general sobre la igualdad del número cromático y el número cromático prescrito para multigrafos arbitrarios sin bucles. Esta hipótesis permanece abierta. $GRAMO$ $k$ $k$ $K_{{n,n}}$ $norte$

Muchas variaciones del problema de coloración de vértices que se han estudiado se han extendido a la coloración de bordes. Por ejemplo, el problema de coloración de borde completo es una variante de coloración completa , la coloración correcta de vértices, en la que cualquier par de colores debe estar presente al menos una vez en el conjunto de vértices conjugados, y el problema es maximizar el número total de vértices. colores [40] . La coloración estricta de bordes es una variante de la coloración estricta de bordes , en la que dos bordes con vértices adyacentes deben tener colores diferentes [41] . La coloración estricta de los bordes se usa en el diseño del canal para redes inalámbricas [42] . Una coloración de línea acíclica es una variante de una coloración acíclica en la que dos colores cualesquiera forman un subgrafo acíclico (es decir, un bosque) [43] .

En 2008 [28] , se estudió una coloración de 3 líneas de gráficos cúbicos con la propiedad adicional de que dos ciclos de dos colores no tienen más de un borde común; en particular, se demostró que la existencia de tal coloración es equivalente a la existencia de un gráfico que se dibuja en una red de enteros tridimensional con bordes en líneas , paralelas a los ejes de coordenadas, y cada línea contiene como máximo dos vértices. Sin embargo, como en el caso del problema estándar de coloración de 3 bordes, encontrar una coloración de este tipo es un problema NP-completo.

La coloración total es un tipo de coloración que combina la coloración de vértices y bordes, en la que se colorean tanto los vértices como los bordes. Cualquier vértice y la arista de la que es el final, o dos aristas adyacentes deben tener colores diferentes, así como dos vértices adyacentes. Existe la conjetura (combinando el teorema de Vizing y el teorema de Brooks ) de que cualquier gráfico tiene una coloración total en la que el número de colores no supera la potencia máxima más dos. La hipótesis no ha sido probada.

Si un gráfico de 3 regulares en una superficie se puede colorear con 3 bordes, su gráfico dual forma una triangulación de la superficie, que también se puede colorear con los bordes (aunque, en general, la coloración de líneas no es correcta) en el sentido de que cada el triángulo se colorea con tres colores, una arista por color. Se pueden usar otros colores y orientaciones de triángulos, junto con otras restricciones locales sobre cómo se distribuyen los colores sobre los vértices o las caras de una triangulación, para codificar ciertos tipos de objetos geométricos. Por ejemplo, las subdivisiones rectangulares (partes de una partición rectangular de un rectángulo en rectángulos más pequeños, donde tres rectángulos se encuentran en cada punto) se pueden describir combinatoriamente mediante "marcas regulares", una coloración de dos colores de los bordes de un gráfico de triangulación dual a una subdivisión rectangular, con la restricción de que las aristas adyacentes a cada vértice formen cuatro grupos de aristas que van (en el sentido de las agujas del reloj) en una fila. Dentro de cada grupo, los bordes están pintados del mismo color y tienen la misma dirección. Esta marca es dual al colorido del propio refinamiento, en el que los bordes verticales tienen un color y los bordes horizontales otro. Se pueden usar restricciones locales similares en el orden de los bordes coloreados para un vértice para codificar la incrustación de gráficos planos en una cuadrícula formada por líneas rectas y poliedros 3D con caras paralelas a los planos de coordenadas. Para cada uno de estos tres tipos de marcas regulares, el conjunto de marcas regulares forma una red distributiva , que se puede usar para enumerar rápidamente todas las estructuras geométricas basadas en el mismo gráfico, o encontrar una estructura que satisfaga restricciones adicionales [44] .

Un autómata finito determinista se puede representar como un gráfico dirigido en el que cada vértice tiene el mismo grado exterior de vértices y en el que las aristas están coloreadas de tal manera que dos aristas cualesquiera con el mismo vértice inicial tienen colores diferentes. El problema de coloración de carreteras es un problema de coloración de líneas para un gráfico dirigido con el mismo grado de salida, de modo que el autómata resultante tiene una palabra de sincronización . Trachtman ( Trachtman 2009 ) resolvió el problema de coloración de carreteras demostrando que tal coloración se puede encontrar si el gráfico dado es fuertemente conexo y aperiódico . $d$

El teorema de Ramsey se refiere al problema de colorear los bordes de un gran gráfico completo para evitar crear subgráficos monocromáticos completos de un tamaño determinado . Según el teorema, existe un número tal que para el color especificado es imposible. Por ejemplo, , lo que significa que si los bordes del gráfico son de 2 colores, siempre habrá un triángulo monocromático. $k$ $K_n$ $Kansas}$ $s$ $R_{k}(s)$ $n\geq R(s)$ $R_{2}(3)=6$ $K_{6}$

Aplicaciones

La coloración de líneas de gráficos completos se puede utilizar para dividir el calendario de torneos de todos contra todos en varias rondas, de modo que cada pareja juegue en una de las rondas. En esta aplicación, los vértices corresponden a los participantes en el torneo y los bordes corresponden a los juegos. El color de los bordes corresponde a los círculos del torneo [45] . Se puede usar una técnica de coloración similar para otros programas deportivos en los que no todos necesariamente juegan con todos. Por ejemplo, en la Liga Nacional de Fútbol (Estados Unidos, Fútbol Americano ), las parejas de equipos que jugarán en un año determinado están determinadas por los resultados de los equipos en el año anterior, y se aplica el algoritmo de coloración de bordes al gráfico. formado por el conjunto de estas parejas para repartir los juegos a lo largo del fin de semana, según el cual se desarrollan los juegos [46] . Para esta aplicación, el teorema de Vizing significa que no importa qué conjunto de emparejamientos se elija (siempre que dos equipos no jueguen dos veces en una temporada), siempre es posible encontrar un calendario que capture como máximo un fin de semana adicional (en comparación con el número de juegos que juega un equipo).

El cronograma para una línea abierta es un problema de planificación de un proceso de producción , en el cual hay muchos objetos que necesitan ser fabricados. Cada objeto debe pasar por algunos procedimientos (en cualquier orden) y cada trabajo debe realizarse en una máquina específica, mientras que la máquina solo puede realizar un procedimiento a la vez. Si todos los trabajos tienen la misma longitud, entonces el problema se puede plantear como la coloración de líneas de un gráfico bipartito, en el que los vértices de una parte representan los objetos que se van a fabricar y los vértices de la otra parte del gráfico representan máquinas de procesamiento. . Los bordes representan el trabajo a realizar y los colores representan los intervalos de tiempo en los que se debe realizar el trabajo. Dado que la coloración de líneas de un gráfico bipartito se puede realizar en tiempo polinomial, lo mismo es cierto para el caso especial especificado de programación de líneas abiertas [47] .

En 2005 [48] , se estudió el problema de programación de conexiones para un protocolo de comunicación de acceso múltiple por división de tiempo en redes de sensores inalámbricos como una variante de coloración de bordes. En este problema, debe elegir los intervalos de tiempo para los bordes de la red inalámbrica para que cada vértice de la red pueda comunicarse con los vértices vecinos sin influencia mutua. El uso de colores de borde estrictos (con dos intervalos de tiempo para cada color de borde, uno en cada dirección) resuelve el problema, pero el número de intervalos utilizados puede ser más del necesario. En su lugar, estaban buscando una coloración del gráfico dirigido formado al reemplazar cada borde no dirigido con dos arcos dirigidos, con cada arco con un color diferente de los colores de los arcos que salen de y sus vecinos . Propusieron un algoritmo heurístico para resolver este problema, basado en un algoritmo distribuido para colorear los bordes seguido de un proceso de corrección de programación para eliminar posibles interferencias mutuas. $ultravioleta$ $v$ $v$ $({\Delta}+1)$

En la comunicación por fibra óptica , el problema de asignación de color es el problema de asignar una frecuencia de luz a un par de vértices que requieren comunicación y caminos a través de la red de fibra para cada par, con la restricción de que no hay dos caminos que compartan el mismo segmento de fibra. y la misma frecuencia. Las rutas que pasan por el mismo conmutador, pero no por el mismo segmento de fibra, pueden tener la misma frecuencia. Si la red se construye como una estrella con un solo interruptor en el centro, que está conectado por una fibra separada a cada nodo de la red, el problema de asignación de colores se puede modelar exactamente como el problema de colorear los bordes de un gráfico o multigrafo. en el que los nodos de comunicación forman nodos gráficos, los pares de nodos que necesitan intercambio de información forman arcos, y la frecuencia que se puede usar para cada par de nodos corresponde a la coloración de los arcos en el problema de coloración. Para redes de comunicación que tienen una topología de árbol más general, las soluciones locales a los problemas de asignar un color de camino a las estrellas formadas por cada comunicador pueden juntarse para obtener una única solución global [49] .

Temas abiertos

Jensen y Toft [50] enumeraron 23 problemas abiertos relacionados con la coloración de los bordes. Éstos incluyen:

La hipótesis de Goldberg [51] de que el índice cromático y el índice fraccionario no difieren en más de uno, lo que permitiría aproximar el índice cromático con un error de un color en tiempo polinomial.
Algunas conjeturas de Jacobsen ( Jakobsen ) y otros sobre la estructura de grafos críticos para la coloración de líneas de grafos de clase 2, de modo que cualquier subgrafo tiene un grado máximo más bajo o tiene clase 1. Jacobsen supuso originalmente que todos los gráficos críticos tienen un número impar de vértices, pero, en última instancia, la suposición es refutada. Varias otras conjeturas más débiles que esta, así como conjeturas que limitan el número de vértices de grafos críticos y multigrafos críticos, permanecen abiertas.
El problema de Vizing de clasificación de grados máximos, que es posible para gráficos planos de clase 2.
Conjetura sobre grafos de Hilton desbordados (AJW Hilton), que establece que un grafo con grado al menos tiene clase 1 o contiene un subgrafo del mismo grado que el grafo original, y para un número impar de vértices tal que el número de aristas del el subgrafo es mayor que . Cercana a esta es la conjetura de Herbert Grötsch y Paul Seymour sobre grafos planos en lugar de grafos de alto grado. $n/3$ $\Delta$ $k$ $\Delta(k-1)/2$
La conjetura de Chetwynd y Hilton (posiblemente arraigada en el trabajo anterior de Dirac de que un gráfico regular con un número par de vértices y grado tiene al menos clase 1. $norte$ $n/2$
La conjetura de Claudy Berge y Delbert Fulkerson de que los multigrafos regulares de 6 formados al duplicar cada borde de un gráfico simple sin puente de 3 regulares pueden colorearse con seis colores.
La conjetura de Fiorini y Wilson de que cualquier gráfico plano sin triángulos , que no sea la garra K 1,3 , no es únicamente coloreable de aristas con 3 colores.

También es digna de mención una conjetura más moderna: si es un -multigrafo plano regular, entonces es coloreable por aristas si y sólo si es impar conectado por aristas. Esta conjetura puede considerarse como una generalización del problema de los cuatro colores para . Maria Chudnovskaya , Katherine Edwards y Paul Seymour demostraron que un multigrafo plano regular de 8 tiene el número cromático de borde 8 [52] . $GRAMO$ $d$ $GRAMO$ $d$ $GRAMO$ $d$ $re=3$

Notas

↑ Soifer, 2008 , problema 16.4, p. 133.
↑ Soifer, 2008 .
↑ Soifer, 2008 , problema 16.5, p. 133. El hecho de que necesites colores o colores se deriva del teorema de Vizing . $norte$ $(n-1)$
↑ Biggs, 1972 .
↑ Biggs, 1972 ; Meredith, Lloyd 1973 ; Biggs, 1979 .
↑ 12 Soifer , 2008 , pág. 134.
↑ 1 2 König, 1916 .
↑ Erdős, Wilson, 1977 .
↑ Hollier, 1981 .
↑ Vising, 1965 .
↑ Lijadoras, Zhao, 2001 .
↑ Tait, 1880 ; Apel, Haken, 1976 .
↑ Soifer, 2008 , pág. 136.
↑ Shannon, 1949 .
↑ 1 2 Cole, Ost, Schirra, 2001 .
↑ Cole, Hopcroft, 1982 .
↑ Alon, 2003 .
↑ Gabov, 1976 .
↑ Cole, Kovalik, 2008 .
↑ Misra, Grise, 1992 .
↑ Gabov et al., 1985 .
↑ Karlof, Schmois, 1987 .
↑ Bar-Noy, Motwani, Naor, 1992 .
↑ Bahmani, Mehta, Motwani, 2010 .
↑ Goldberg 1973 , Andersen 1977 , Seymour 1979 .
↑ Chen, Yu, Zang, 2011 .
↑ Kovalik, 2009 .
↑ 1 2 Epstein, 2008 .
↑ Björklund, Husfeld, Koivisto, 2009 .
↑ Zhou, Nakano, Nishizeki, 1996 .
↑ Nemhauser, Parque, 1991 .
↑ Schwenk, 1989 .
↑ Folkman, Fulkerson, 1969 .
↑ Bosack, 1972 .
↑ Richter, 2011 .
↑ Akiyama, Ikzu, Harari 1980 , Habib, Peroshe 1982 , Horak, Nipel 1982 .
↑ NashWilliams, 1964 .
↑ Gabov, Westerman, 1992 .
↑ Galvín, 1995 .
↑ Bosak, Neshetril, 1976 .
↑ Fouquet, Jolivet 1983 ; Mahdián, 2002 ; Friz, Krivelevich, Sudakov, 2005 ; Craston, 2006 .
↑ Barret et al., 2006 .
↑ Alon, Sudakov, Zaks, 2001 , Muthu, Narayanan, Subramanyan, 2007 .
↑ Epstein, 2010 .
↑ Burke, Werra, Kingston, 2004 .
↑ Skiena, 2008 .
↑ Williamson et al., 1997 .
↑ Gandham, Davande, Prakash, 2005 .
↑ Elebach, Jensen, 2001 .
↑ Jensen, Toft, 1995 .
↑ Goldberg, 1973 .
↑ María Chudnovsky, Katherine Edwards, Paul Seymour. Gráficos planos regulares de ocho colores de borde (neopr.) . - 2012. - 13 de enero.

Enlaces

Jin Akiyama, Geoffrey Exoo, Frank Harary. Cobertura y empaquetamiento en gráficos. tercero Invariantes cíclicos y acíclicos // Mathematica Slovaca. - 1980. - T. 30 , núm. 4 . - S. 405-417 .
Noga Alon. Un algoritmo simple para colorear bordes de multigrafos bipartitos // Letras de procesamiento de información. - 2003. - T. 85 , núm. 6 _ - S. 301-302 . - doi : 10.1016/S0020-0190(02)00446-5 .
Noga Alon, Benny Sudakov, Ayal Zaks. Coloraciones de bordes acíclicos de gráficos // Journal of Graph Theory. - 2001. - T. 37 , núm. 3 . - S. 157-167 . -doi : 10.1002/ jgt.1010 .
Lars Dovling Andersen. Sobre la coloración de los bordes de los gráficos // Mathematica Scandinavica. - 1977. - T. 40 , núm. 2 . - S. 161-175 . . Como se cita en [1]
K. Appel, W. Haken. Cada mapa plano tiene cuatro colores // Boletín de la Sociedad Matemática Estadounidense. - 1976. - vol. 82 , edición. 5 . - Pág. 711-712 . -doi : 10.1090 / S0002-9904-1976-14122-5 .
Bahman Bahmani, Aranyak Mehta, Rajeev Motwani. Actas del vigésimo primer simposio anual ACM-SIAM sobre algoritmos discretos (SODA '10). - 2010. - S. 31-39 .
Amotz Bar-Noy, Rajeev Motwani, Joseph Naor. El algoritmo codicioso es óptimo para colorear bordes en línea // Cartas de procesamiento de información. - 1992. - T. 44 , núm. 5 . - S. 251-253 . -doi : 10.1016 / 0020-0190(92)90209-E .
C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, S. Thite, S. Thulasidasan. proc. Cuarta Conferencia Internacional Anual IEEE sobre Informática Pervasiva y Talleres de Comunicaciones (PerCom Workshops 2006). - 2006. - S. 106 . — ISBN 0-7695-2520-2 . -doi : 10.1109/ PERCOMW.2006.129 .
Norman Biggs. Problemas de Investigación / Richard K. Guy. — Revista Matemática Estadounidense. - 1972. - T. 79. - S. 1018-1020.
Norman Biggs. Segunda Conferencia Internacional sobre Matemática Combinatoria // Anales de la Academia de Ciencias de Nueva York. - 1979. - T. 319 . - S. 71-81 . -doi : 10.1111 / j.1749-6632.1979.tb32775.x .
Andreas Bjorklund, Thore Husfeldt, Mikko Koivisto. Establecer particiones a través de inclusión-exclusión // SIAM Journal on Computing. - 2009. - T. 39 , núm. 2 . - S. 546-563 . -doi : 10.1137/ 070683933 .
Juraj Bosak. Índice cromático de gráficos finitos e infinitos // Revista matemática checoslovaca. - 1972. - T. 22 (97) . - S. 272-290 .
Juraj Bosak, Jaroslav Nesetril. Coloraciones completas y pseudocompletas de un gráfico // Matematicky Casopis Slovenskej Akademie Vied. - 1976. - T. 26 , núm. 3 . - S. 171-184 .
E. Burke, D. DeWerra, J. Kingston. {{{título}}} / JL Gross, J. Yellen. - Prensa CRC, 2004. - S. 462 . - ISBN 978-1-58488-090-5 .
Guantao Chen, Xingxing Yu, Wenan Zang. Aproximación del índice cromático de multigrafos // Journal of Combinatorial Optimization. - 2011. - T. 21 , núm. 2 . - S. 219-246 . -doi : 10.1007 / s10878-009-9232-y .
Richard Cole, John Hopcroft. Gráficos bipartitos coloreados al borde // SIAM Journal on Computing. - 1982. - T. 11 , núm. 3 . - S. 540-546 . -doi : 10.1137/ 0211043 .
Richard Cole, Lukasz Kowalik. Nuevos algoritmos de tiempo lineal para gráficos planos de coloración de bordes // Algorithmica. - 2008. - T. 50 , núm. 3 . - S. 351-368 . -doi : 10.1007/ s00453-007-9044-3 .
Richard Cole, Kirstin Ost, Stefan Schirra. Multigrafos bipartitos de coloración de bordes en el tiempo // Combinatorica . - 2001. - T. 21 , núm. 1 . - Pág. 5-12 . -doi : 10.1007/ s004930170002 . $O(E\logD)$
Daniel W. Cranston. Fuerte coloración de bordes de gráficos con grado máximo 4 usando 22 colores // Matemáticas discretas . - 2006. - T. 306 , núm. 21 . - S. 2772-2778 . -doi : 10.1016/ j.disco.2006.03.053 .
David Epstein. proc. 16 Int. Síntoma Dibujo gráfico / Ioannis G. Tollis, Marizio Patrignani. - Heraklion, Creta, 2008. - T. 5417. - S. 78-89. — (Apuntes de clase en informática).
David Epstein. proc. 22ª Conferencia Canadiense sobre Geometría Computacional (CCCG 2010). — 2010.
Paul Erdos, Robin J. Wilson. Nota sobre el índice cromático de casi todos los gráficos // Journal of Combinatorial Theory . - 1977. - T. 23 , núm. 2-3 . - S. 255-257 . - doi : 10.1016/0095-8956(77)90039-9 .
Thomas Erlebach, Klaus Jansen. La complejidad de la coloración de rutas y la programación de llamadas // Ciencias de la computación teórica. - 2001. - T. 255 , núm. 1-2 . - S. 33-50 . - doi : 10.1016/S0304-3975(99)00152-8 .
S. Fiorini, RJ Wilson. Coloraciones de borde de gráficos. - Londres: Pitman, 1977. - V. 16. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Jon Folkman, DR Fulkerson. Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967). - Chapel Hill, Carolina del Norte: Univ. Prensa de Carolina del Norte, 1969, págs. 561-577.
JL Fouquet, J.-L. Jolivet. Fuerte coloración de bordes de gráficos y aplicaciones a multi -gons // Ars Combinatoria. - 1983. - T. 16 , núm. A._ _ - S. 141-150 . $k$
Alan M. Frieze, Michael Krivelevich, Benny Sudakov. El fuerte índice cromático de grafos aleatorios // SIAM Journal on Discrete Mathematics . - 2005. - T. 19 , núm. 3 . - S. 719-727 (electrónico) . -doi : 10.1137/ S0895480104445757 .
Harold N. Gabow. Uso de particiones de Euler para bordear multigrafos bipartitos de color // Revista internacional de informática y ciencias de la información. - 1976. - V. 5 , núm. 4 . - S. 345-355 . -doi : 10.1007/ BF00998632 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmos para gráficos de coloración de bordes. — Universidad de Tohoku, 1985.
Harold N. Gabow, Herbert H. Westermann. Bosques, marcos y juegos: algoritmos para sumas matroid y aplicaciones // Algorithmica. - 1992. - T. 7 , nº. 5-6 . - S. 465-497 . -doi : 10.1007/ BF01758774 .
F. Galvín. El índice cromático de lista de un multigrafo bipartito // Journal of Combinatorial Theory . - 1995. - T. 63 , núm. 1 . - S. 153-158 . -doi : 10.1006/ jctb.1995.1011 .
S. Gandham, M. Dawande, R. Prakash. proc. 24 INFOCOM. - 2005. - T. 4 . - S. 2492-2501 . — ISBN 0-7803-8968-9 . -doi : 10.1109/ INFCOM.2005.1498534 .
MK Goldberg. Multigraphs con un índice cromático que es casi máximo // Diskret. Analiz.. - 1973. - Edición. 23 . - S. 3-7, 72 . . Como se cita en [1] .
M. Habib, B. Peroche. Algunos problemas de arboricidad lineal // Matemáticas Discretas. - 1982. - T. 41 , núm. 2 . - S. 219-220 . - doi : 10.1016/0012-365X(82)90209-6 .
Ian Holyer. La integridad NP de la coloración de bordes // SIAM Journal on Computing . - 1981. - T. 10 , núm. 4 . - S. 718-720 . -doi : 10.1137/ 0210055 .
Peter Horak, Ludovit Niepel. Una breve prueba de un teorema de arboricidad lineal para grafos cúbicos // Acta Mathematica Universitatis Comeniae. - 1982. - T. 40/41 . - S. 275-277 .
Tommy R. Jensen, Bjarne Toft. Problemas para colorear gráficos. - Nueva York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
Howard J. Karloff, David Shmoys. Algoritmos paralelos eficientes para problemas de coloración de bordes // Journal of Algorithms. - 1987. - T. 8 , núm. 1 . - S. 39-52 . - doi : 10.1016/0196-6774(87)90026-5 .
Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Mathematische Annalen . - 1916. - T. 77 , núm. 4 . - S. 453-465 . -doi : 10.1007/ BF01456961 .
Lukasz Kowalik. Coloración de bordes mejorada con tres colores // Ciencias de la computación teórica. - 2009. - T. 410 , núm. 38-40 . - S. 3733-3742 . -doi : 10.1016/ j.tcs.2009.05.005 .
Mohammad Mahdian. Sobre la complejidad computacional de la coloración de bordes fuertes // Matemáticas aplicadas discretas. - 2002. - T. 118 , núm. 3 . - S. 239-248 . - doi : 10.1016/S0166-218X(01)00237-2 .
Guy HJ Meredith, E. Keith Lloyd. Los futbolistas de Croam // Journal of Combinatorial Theory . - 1973. - T. 15 , núm. 2 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
J. Misra, D. Gries. Una demostración constructiva del teorema de Vizing // Cartas de procesamiento de información . - 1992. - T. 41 , núm. 3 . - S. 131-133 . -doi : 10.1016 / 0020-0190(92)90041-S .
Rahul Muthu, N. Narayanan, C. R. Subramanian. Límites mejorados en la coloración de bordes acíclicos // Matemáticas discretas . - 2007. - T. 307 , núm. 23 . - S. 3063-3069 . -doi : 10.1016/ j.disco.2007.03.006 .
Crispin Nash-Williams. Descomposición de grafos finitos en bosques // Revista de la Sociedad Matemática de Londres. - 1964. - T. 39 .
George Nemhauser, Parque Sungsoo. Un enfoque poliédrico para colorear los bordes // Cartas de investigación operativa. - 1991. - T. 10 , núm. 6 _ - S. 315-322 . - doi : 10.1016/0167-6377(91)90003-8 .
David A. Richter. proc. 18º Simposio Internacional de Dibujo Gráfico (GD 2010) / Ulrik Brandes, Sabine Cornelsen. - Springer-Verlag, 2011. - T. 6502. - S. 353-364. — (Apuntes de clase en informática). - ISBN 978-3-642-18468-0 . -doi : 10.1007 / 978-3-642-18469-7_32 .
Daniel P. Sanders, Yue Zhao. Los gráficos planos de máximo grado siete son de clase I // Journal of Combinatorial Theory . - 2001. - T. 83 , núm. 2 . - S. 201-212 . -doi : 10.1006/ jctb.2001.2047 .
PD Seymour. Sobre multicolores de gráficos cúbicos y conjeturas de Fulkerson y Tutte // Actas de la London Mathematical Society. - 1979. - T. 38 , núm. 3 . - S. 423-460 . -doi : 10.1112 / plms/s3-38.3.423 .
Allen J. Schwenk. Enumeración de ciclos hamiltonianos en ciertos gráficos de Petersen generalizados // Journal of Combinatorial Theory . - 1989. - T. 47 , núm. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
Claudio Shannon. Un teorema sobre cómo colorear las líneas de una red // J. Math. Física. - 1949. - T. 28 . - S. 148-151 .
Steven S. Skiena. Manual de diseño de algoritmos . - Springer-Verlag, 2008. - S. 548 -550 . - ISBN 978-1-84800-069-8 . -doi : 10.1007 / 978-1-84800-070-4_16 . . Véase también [1] en el repositorio de algoritmos de Stony Brook.
Alejandro Sofer. El libro de colorear matemático. - Springer-Verlag, 2008. - ISBN 978-0-387-74640-1 .
PG Tait. Comentarios sobre los colores de los mapas // Proc. R. Soc. Edimburgo. - 1880. - T. 10 . - S. 729 .
Trachtman. El problema del coloreado de la carretera // Israel Journal of Mathematics. - 2009. - T. 172 , núm. 1 . - S. 51-60 . -doi : 10.1007/ s11856-009-0062-5 . -arXiv : 0709.0099 . _
VG Vising. Sobre una estimación de la clase cromática de un p -graph // Diskret. Analiz.. - 1964. - T. 3 . - S. 25-30 .
VG Vising. Gráficos críticos con clase cromática dada // Methody Diskret. Analiz.. - 1965. - V. 5 . - S. 9-17 . . (En ruso.)
DP Williamson, LA Hall, JA Hoogeveen, CAJ Hurkens, JK Lenstra, SV Sevast'janov, DB Shmoys. Horarios cortos de taller // Investigación de operaciones. - 1997. - T. 45 , núm. 2 . - S. 288-294 . doi : 10.1287 / opre.45.2.288 . . _
Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki. Árboles parciales de coloración de bordes // Journal of Algorithms. - 1996. - T. 21 , núm. 3 . - S. 598-617 . -doi : 10.1006/ jagm.1996.0061 . $k$

↑ 1 2 Chen, Yu, Zang, 2011 .