Coloración de bordes

En teoría de grafos , una coloración adecuada de las aristas de un grafo consiste en asignarles colores de tal manera que no haya dos aristas incidentes del mismo color. Por ejemplo, la figura de la derecha muestra una coloración de las aristas de un grafo con los colores rojo, azul y verde. Las coloraciones de aristas son uno de los diferentes tipos de coloración de grafos . El problema de la coloración de aristas plantea si es posible colorear las aristas de un grafo dado utilizando como máximo k colores diferentes, para un valor dado de k , o con el menor número de colores posible. El número mínimo de colores requerido para las aristas de un grafo dado se denomina índice cromático del grafo.

Según el teorema de Vizing , el número de colores necesarios para colorear las aristas de un grafo simple es su grado máximo Δ o Δ + 1. Para algunos grafos, como los bipartitos y los planares de alto grado , el número de colores es siempre Δ , y para los multigrafos , puede llegar a 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 aristas es NP-difícil y los algoritmos más rápidos conocidos para ello requieren un tiempo exponencial. Se han estudiado muchas variaciones del problema de coloración de aristas, en las que la asignación de colores a las aristas debe satisfacer otras condiciones además de la no adyacencia. Las coloraciones de aristas tienen aplicaciones en problemas de planificación y en la asignación de frecuencias para redes de fibra óptica .

Un grafo cíclico puede tener sus aristas coloreadas con dos colores si la longitud del ciclo es par: simplemente se alternan los dos colores alrededor del ciclo. Sin embargo, si la longitud es impar, se necesitan tres colores. ^{[ 1 ]}

Un grafo completo K _n con n vértices se puede colorear por 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: colocar n puntos en los vértices y el centro de un polígono regular de ( n − 1) lados. Para cada clase de color, incluir una arista desde el centro a 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 de 1/ n del total. ^{[ 2 ]}

Varios autores han estudiado las coloraciones de aristas 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 las aristas representan posibles emparejamientos de estos equipos (con un jugador que queda como "el que queda fuera" para arbitrar el juego). El caso en que n = 3 da el conocido grafo de Petersen . Como explica Biggs (1972) el problema (para n = 6 ), los jugadores desean encontrar un calendario para estos emparejamientos de tal manera que cada equipo juegue cada uno de sus seis juegos en días diferentes de la semana, con los domingos libres para todos los equipos; es decir, formalizando matemáticamente el problema, desean encontrar una coloración de 6 aristas del grafo impar 6-regular O ₆ . Cuando n es 3, 4 u 8, una coloración de aristas de O _n requiere n + 1 colores, pero cuando es 5, 6 o 7, solo se necesitan n colores. ^{[ 3 ]}

Al igual que con su contraparte de vértices , una coloración de aristas de un grafo, cuando se menciona sin ninguna especificación, siempre se asume que es una coloración propia de las aristas, lo que significa que no se asigna el mismo color a dos aristas adyacentes. Aquí, dos aristas distintas se consideran adyacentes cuando comparten un vértice común. Una coloración de aristas de un grafo G también puede considerarse equivalente a una coloración de vértices del grafo de líneas L ( G ) , el grafo que tiene un vértice por cada arista de G y una arista por cada par de aristas adyacentes en G.

Una coloración de aristas adecuada con k colores diferentes se denomina coloración de aristas k (adecuada). Un grafo al que se le puede asignar una coloración de aristas k se denomina colorable de aristas k . El número mínimo de colores necesarios en una coloración de aristas (adecuada) de un grafo G es el índice cromático , o número cromático de aristas, χ ′ ( G ) . El índice cromático también se escribe a veces utilizando la notación χ ₁ ( G ) ; en esta notación, el subíndice uno indica que las aristas son objetos unidimensionales. Un grafo es k -cromático de aristas si su índice cromático es exactamente k . El índice cromático no debe confundirse con el número cromático χ( G ) o χ ₀ ( G ) , el número mínimo de colores necesarios en una coloración de vértices adecuada de G . 

Salvo indicación contraria, se asume 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 extremos y pueden existir bucles. En muchos problemas de coloración de aristas, los grafos simples se comportan de manera diferente a los multigrafos, y se requiere especial atención para extender los teoremas sobre coloración de aristas de grafos simples al caso de los multigrafos.

En un grafo G, un emparejamiento es un conjunto de aristas, ninguna de las cuales es adyacente a otra. Un emparejamiento perfecto es aquel que incluye aristas que tocan todos los vértices del grafo, y un emparejamiento máximo es aquel que incluye tantas aristas como sea posible. En una coloración de aristas, el conjunto de aristas con un mismo color debe ser completamente no adyacente entre sí, de modo que formen un emparejamiento. Es decir, una coloración de aristas propia equivale a una partición del grafo en emparejamientos disjuntos.

Si el tamaño de un emparejamiento máximo en un grafo dado es pequeño, entonces se necesitarán muchos emparejamientos para cubrir todas las aristas del grafo. Expresado de manera más formal, este razonamiento implica que si un grafo tiene m aristas en total, y si como máximo β aristas pueden pertenecer a un emparejamiento máximo, entonces cada coloración de aristas 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 aristas. En este grafo, no puede haber un emparejamiento perfecto; porque, si el vértice central está emparejado, los vértices restantes no emparejados pueden agruparse en tres componentes conexas diferentes con cuatro, cinco y cinco vértices, y las componentes con un número impar de vértices no pueden emparejarse perfectamente. Sin embargo, el grafo tiene emparejamientos máximos con siete aristas, por lo que β = 7 . Por lo tanto, el número de colores necesarios para colorear las aristas del grafo es al menos 24/7, y como 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, esta cota inferior puede usarse 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 del apretón de manos , k debe ser par. Sin embargo, la desigualdad χ ′ ≥ 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 con 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.

Dado que el problema de determinar si un grafo pertenece a la clase 1 es NP-completo , no se conoce ningún algoritmo de tiempo polinomial para colorear las aristas de todos los grafos con un número óptimo 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, no siempre utilizan un número óptimo de colores o no siempre se ejecutan en tiempo polinomial.

Un grafo es unívocamente k -coloreable si solo hay una forma de particionar las aristas en k clases de color, ignorando las k ! posibles permutaciones de los colores. Para k ≠ 3 , los únicos grafos unívocamente k -coloreables son caminos, ciclos y estrellas , pero para k = 3 otros grafos también pueden ser unívocamente k -coloreables. Todo grafo unívocamente 3-coloreable 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 3-coloreables, como los grafos de Petersen generalizados G (6n + 3, 2) para n ≥ 2. El único grafo no planar unívocamente 3-coloreable 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 ₁ , m ₂ , m ₃ , ... con la propiedad de que existe una coloración de aristas adecuada de un grafo G dado con m ₁ aristas del primer color, m ₂ 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, partiendo de 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 grafo tiene una coloración de aristas equitativa , una coloración de aristas con un número óptimo de colores en la que cada par de clases de color difieren en tamaño en como máximo 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 una representación gráfica de un grafo cúbico dado con las propiedades de que todas las aristas en la representación tengan una de tres pendientes diferentes y que no haya dos aristas que se encuentren en la misma línea. Si existe tal representación, entonces claramente las pendientes de las aristas pueden usarse como colores en una coloración de 3 aristas del grafo. Por ejemplo, la representación gráfica del grafo de utilidad K _3,3 como las aristas y diagonales largas de un hexágono regular representa una coloración de 3 aristas del grafo de esta manera. Como muestra Richter, un grafo bipartito simple 3-regular, con una coloración de Tait dada, tiene una representación gráfica de este tipo que representa la coloración dada si y solo si el grafo es 3-arista-conexo . 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 es 3-arista-conexa, y si la eliminación de cualquier par de aristas monocromáticas da como resultado un subgrafo que sigue siendo no bipartito. Todas estas condiciones pueden comprobarse fácilmente en tiempo polinomial; sin embargo, el problema de comprobar si un grafo 4-regular con 4 aristas coloreadas tiene un dibujo con aristas de cuatro pendientes, que representan los colores mediante pendientes, es completo para la teoría existencial de los reales , una clase de complejidad al menos tan difícil como ser NP-completa.

Además de estar relacionado con el grado máximo y el número máximo de emparejamientos 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 particionar las aristas del grafo. Un emparejamiento es un tipo especial de bosque lineal, y en la otra dirección, cualquier bosque lineal puede tener 2 colores en sus aristas, por lo que para cada G se cumple que la( G ) ≤ χ ′ ( G ) ≤ 2la( G ) . La conjetura de Akiyama (llamada así por Jin Akiyama ) afirma que${\displaystyle \mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil }$, de lo cual se seguiría con mayor fuerza que 2 la( G ) − 2 ≤ χ ′ ( G ) ≤ 2 la( G ) . Para grafos de grado máximo tres, la( G ) siempre es exactamente dos, por lo que en este caso la cota χ ′ ( G ) ≤ 2 la( G ) coincide con la cota dada por el teorema de Vizing. ^{[ 18 ]}

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

La arboricidad de un grafo es el número mínimo de colores necesarios para que las aristas de cada color no tengan ciclos (en lugar de, como en el problema estándar de coloración de aristas, no tener pares de aristas adyacentes). Es decir, es el número mínimo de bosques en los que se pueden particionar las aristas del grafo. ^{[ 19 ]} A diferencia del índice cromático, la arboricidad de un grafo se puede calcular en tiempo polinomial. ^{[ 20 ]}

El problema de coloración de aristas por lista consiste en dar un grafo donde cada arista está asociada a una lista de colores, y encontrar una coloración adecuada en la que el color de cada arista se extraiga de su lista. El índice cromático de lista de un grafo G es el número más pequeño k que tiene la propiedad de que, independientemente de 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 existe una coloración posible. Por lo tanto, el índice cromático de lista siempre es al menos tan grande como el índice cromático. El teorema de Dinitz sobre la completación de cuadrados latinos parciales puede reformularse como la afirmación de que el número cromático de aristas por lista del grafo bipartito completo K _n,n es igual a su número cromático de aristas, n . Galvin (1995) resolvió la conjetura demostrando, de forma más general, que en todo 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 forma más general, para multigrafos arbitrarios sin bucles propios; esta conjetura sigue abierta. 

Muchas otras variaciones comúnmente estudiadas de la coloración de vértices también se han extendido a las coloraciones de aristas. Por ejemplo, la coloración completa de aristas es la variante de coloración completa de aristas , una coloración de aristas propia 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 fuerte de aristas es la variante de coloración fuerte de aristas , una coloración de aristas en la que cada dos aristas con extremos adyacentes deben tener colores diferentes. ^{[ 22 ]} La coloración fuerte de aristas 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${\displaystyle G}$, denotado por${\displaystyle a'(G)}$, es el número más pequeño de colores necesarios para tener una coloración de borde acíclica adecuada de${\displaystyle G}$Se ha conjeturado que${\displaystyle a'(G)\leq \Delta +2}$, dónde${\displaystyle \Delta }$es el grado máximo de${\displaystyle G}$. ^{[ 25 ]} Actualmente, el límite mejor conocido es${\displaystyle a'(G)\leq \lceil 3.74(\Delta -1)\rceil }$. ^{[ 26 ]} El problema se vuelve más fácil cuando${\displaystyle G}$tiene una gran circunferencia . Más específicamente, hay una constante${\displaystyle c}$de tal manera que si la circunferencia de${\displaystyle G}$es al menos${\displaystyle c\Delta \log \Delta }$, entonces${\displaystyle a'(G)\leq \Delta +2}$. ^{[ 27 ]} Un resultado similar es que para todos${\displaystyle \epsilon >0}$existe un${\displaystyle g}$de tal manera que si${\displaystyle G}$tiene circunferencia al menos${\displaystyle g}$, entonces${\displaystyle a'(G)\leq (1+\epsilon )\Delta }$. ^{[ 28 ]}

Eppstein (2013) estudió las coloraciones de 3 aristas de grafos cúbicos con la propiedad adicional de que ningún par de ciclos bicromáticos comparte más de una arista entre sí. Demostró que la existencia de dicha coloración es equivalente a la existencia de un dibujo del grafo en una cuadrícula tridimensional de enteros, con aristas paralelas a los ejes de coordenadas y cada línea paralela a los ejes conteniendo como máximo dos vértices. Sin embargo, al igual que el problema estándar de coloración de 3 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 formado por un vértice y una arista, o por dos aristas, debe tener colores distintos, al igual que cualquier par de 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 igual al grado máximo más dos, pero esto aún no se ha demostrado.

Si un grafo 3-regular sobre una superficie tiene 3 colores en sus aristas, su grafo dual forma una triangulación de la superficie que también tiene colores en sus aristas (aunque, en general, no de forma propiamente dicha), de manera que cada triángulo tiene una arista de cada color. Se pueden utilizar otros colores 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", un coloreado de dos colores de las aristas de una triangulación dual 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 un coloreado de la propia subdivisión rectangular en el que las aristas verticales tienen un color y las horizontales tienen el otro. Restricciones locales similares sobre el orden en que pueden aparecer aristas coloreadas alrededor de un vértice también pueden usarse para codificar incrustaciones de 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 etiquetado regular, el conjunto de etiquetados regulares de un grafo fijo forma una red distributiva que puede usarse 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 d -coloreadas de tal manera que cada par de aristas con el mismo vértice de origen tienen colores distintos. El problema de coloración de caminos 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 caminos demostrando que dicha coloración puede encontrarse siempre que el grafo dado sea fuertemente conexo y aperiódico .

El teorema de Ramsey trata sobre el 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 s dado . Según el teorema, existe un número R _k ( s ) tal que, siempre que n ≥ R ( s ) , dicha coloración no es posible. Por ejemplo, R ₂ (3) = 6 , es decir, si las aristas del grafo K ₆ están coloreadas con 2 colores, siempre habrá un triángulo monocromático. 

En un grafo con aristas coloreadas, se dice que un camino es un camino arcoíris si ningún color se repite. Un grafo se considera coloreado con colores arcoíris si existe un camino arcoíris entre cualquier par de vértices. Una coloración de 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.

Las coloraciones de aristas de grafos completos pueden usarse 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 grafo corresponden a los competidores en el torneo, las aristas corresponden a los juegos y los colores de las aristas corresponden a las rondas en las que se juegan los juegos. ^{[ 30 ]} Técnicas de coloración similares también pueden usarse para programar otros emparejamientos deportivos que no son todos contra todos; por ejemplo, en la Liga Nacional de Fútbol Americano , 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 aristas al grafo formado por el conjunto de emparejamientos para asignar los 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 que se elija (siempre que ningún equipo juegue dos veces entre sí en la misma temporada), siempre es posible encontrar un calendario que utilice como máximo un fin de semana más que el número de partidos por equipo.

La programación de talleres abiertos es un problema de programación de procesos de producción , en el que existe un conjunto de objetos a fabricar, cada objeto tiene un conjunto de tareas a realizar (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 simultáneamente. Si todas las tareas tienen la misma duración, este problema puede formalizarse como un problema de coloración de aristas en 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 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 ocurre en este caso restringido de programación de talleres abiertos. ^{[ 32 ]}

Gandham, Dawande y Prakash (2005) estudian el problema de la programación de enlaces para protocolos de comunicación de redes de acceso múltiple por división de tiempo en redes de sensores como una variante de la coloración de aristas. En este problema, se deben elegir intervalos de tiempo para las aristas de una red de comunicaciones inalámbricas de manera que cada nodo de la red pueda comunicarse con cada nodo vecino sin interferencias. El uso de una coloración de aristas fuerte (y el uso de dos intervalos de tiempo para cada color de arista, uno para cada dirección) resolvería el problema, pero podría usar más intervalos de tiempo de los necesarios. En cambio, buscan una coloración del grafo dirigido formado al duplicar cada arista no dirigida de la red, con la propiedad de que cada arista dirigida uv tenga un color diferente de las aristas 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 aristas ( Δ + 1) junto con una fase de postprocesamiento que reprograma las aristas que podrían interferir entre sí.

En la comunicación por fibra óptica , el problema de la coloración de rutas consiste en asignar colores (frecuencias de luz) a pares de nodos que desean comunicarse entre sí, y rutas a través de una red de fibra óptica para cada par, con la restricción de que dos rutas que comparten un segmento de fibra no pueden usar la misma frecuencia. Las rutas que pasan por el mismo conmutador de comunicación, pero no por ningún segmento de fibra, pueden usar la misma frecuencia. Cuando la red de comunicaciones está organizada como una red en estrella , con un único conmutador central conectado mediante fibras independientes a cada uno de los nodos, el problema de la coloración de rutas se puede modelar exactamente como un problema de coloración de aristas de un grafo o multigrafo, donde los nodos que se comunican forman los vértices del grafo, los pares de nodos que desean comunicarse forman las aristas del grafo, y las frecuencias que se pueden usar para cada par forman los colores del problema de coloración de aristas. Para redes de comunicaciones con una topología de árbol más general, las soluciones locales de coloración de rutas para las redes en estrella definidas por cada conmutador de la red se pueden combinar para formar una única solución global. ^{[ 33 ]}

Jensen y Toft (1995) enumeran 23 problemas abiertos relacionados con la coloración de aristas. Estos incluyen:

• La conjetura de Goldberg (1973) de que el índice cromático y el índice fraccional están dentro de uno entre sí, lo que permitiría aproximar el índice cromático dentro de un color en tiempo polinomial.
• Varias conjeturas de Jakobsen y otros autores 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 conjeturó originalmente que todos los grafos críticos tienen un número impar de vértices, pero esto fue refutado posteriormente. Varias otras conjeturas que debilitan esta, o que acotan el número de vértices de los grafos críticos y los multigrafos críticos, permanecen abiertas.
• El problema de Vizing de clasificar los grados máximos posibles para grafos planares de clase 2.
• La conjetura del subgrafo sobrecargado de AJW Hilton, que afirma que los grafos con grado al menos n /3 son de clase 1 o contienen un subgrafo con el mismo grado Δ que el grafo original, y con un número impar k de vértices, de tal manera 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 a trabajos anteriores de Gabriel Andrew Dirac ) afirma que los grafos 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 plantea que los multigrafos 6-regulares formados al duplicar cada arista de un grafo simple 3-regular sin puentes pueden colorearse con seis colores en sus aristas.
• Una conjetura de Fiorini y Wilson de que todo grafo planar libre de triángulos , aparte de la garra K _1,3 , no es unívocamente coloreable por 3 aristas .
• Una conjetura de 2012 afirma que si G es un multigrafo planar d -regular, entonces G es d -coloreable por aristas si y solo si G es d -conectado por aristas de forma 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 planar 8-regular tiene un número cromático de aristas de 8. ^{[ 34 ]}