En teoría de grafos , la coloración de los bordes del intervalo es un tipo de coloración de los bordes en el que los bordes están etiquetados por los números enteros en algún intervalo , cada número entero en el intervalo es utilizado por al menos un borde y en cada vértice las etiquetas que aparecen en los bordes incidentes forman un conjunto consecutivo de números distintos.
El concepto de coloración consecutiva de aristas fue introducido con la terminología " coloración de aristas de intervalo" por Asratian y Kamalian en 1987 en su artículo "Coloración de intervalos de aristas de un multigrafo". [1] Desde que se introdujo la coloración de aristas de intervalo de los grafos, los matemáticos han estado investigando la existencia de grafos coloreables de aristas de intervalo, ya que no todos los grafos permiten la coloración de aristas de intervalo. Una familia simple de grafos que permite la coloración de aristas de intervalo es el grafo completo de orden par y un contraejemplo de familia de grafos incluye grafos completos de orden impar. El grafo más pequeño que no permite la coloración de intervalos. Hay grafos pares descubiertos con 28 vértices y grado máximo 21 que no son coloreables de intervalo por Sevast'janov, aunque la coloración de intervalos de grafos con grado máximo comprendido entre cuatro y doce aún se desconoce.
Asratyan y Kamalyan (1987) demostraron que si un gráfico es coloreable por intervalos, entonces el número cromático de las aristas es menor o igual a uno menos que su número de vértices y también observaron que si G es r-regular, entonces G tiene una coloración por intervalos si y solo si G tiene una coloración de arista r adecuada. [1]
Se investiga la coloración de aristas de intervalos en gráficos regulares, gráficos bipartitos que son regulares y no regulares, gráficos planares, entre otras extensiones que se han iniciado en la coloración de aristas de intervalos.
Sea G un grafo de intervalo simple. Una coloración de aristas de un grafo G con colores 1, 2, . . . , t se denomina ""coloración de intervalo t"" si para cada i ∈ {1, 2, . . . , t } hay al menos una arista de G coloreada por i y los colores de las aristas incidentes a cualquier vértice de G son distintos y forman un intervalo de números enteros. [2] Alternativamente, una coloración de aristas de intervalo definida como: Una coloración de aristas de un grafo G con colores 1. . . t es una ' coloración de intervalo t' si se usan 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. Un grafo G es "coloreable en intervalos" si G tiene una coloración de intervalo t para algún número entero positivo t . Sea N el conjunto de todos los grafos coloreables en intervalos. Para un grafo G ∈ N , los valores mínimo y máximo de t para los cuales G tiene una coloración de intervalo t se denotan por w ( G ) y W ( G ), respectivamente. Se dice que una coloración de aristas de intervalo de un grafo es una coloración de aristas de intervalo equitativa si dos clases de color cualesquiera de un grafo difieren en, como máximo, uno.
El conjunto de colores de las aristas que inciden sobre un vértice (x) se denomina espectro de ( x ). Decimos que un subconjunto R de vértices de G tiene una i -propiedad si existe una coloración t de arista propia de G que sea un intervalo sobre R .
Si un grafo sin triángulos G=(V,E) tiene una coloración de intervalo t, entonces t ≤ |V|−1. Asratyan y Kamalian demostraron que si G es coloreable en intervalos, entonces χ'(G)=∆(G). [1] [3]
Petrosyan investigó las coloraciones de intervalos de grafos completos y cubos n-dimensionales y mostró que si n ≤ t ≤ n(n+1)/2, entonces el cubo n-dimensional Qn tiene una coloración de intervalo t. [2] Axenovich demostró que todas las triangulaciones exteriores-planares con más de tres vértices y sin triángulos separadores son coloreables por intervalos. [4] Si G es un grafo regular w(G)=∆(G) y G tiene una coloración de intervalo t para cada t, w(G) ≤ t ≤ W(G).
(1) w ( K m,n ) = m + n − mcd(m, n),
(2) W ( K m,n ) = m + n − 1,
(3) si w ( K m,n ) ≤ t ≤ W ( K m,n ), entonces K m,n tiene una coloración de intervalo t.
w (G[ K m,n ]) ≤ (w(G) + 1)(m + n) − 1 y W (G[ K m,n ]) ≥ (W(G) + 1)(m + n) − 1.
Giaro y Kubale investigaron las coloraciones de los bordes de intervalo de los gráficos planos externos y demostraron que todos los gráficos bipartitos planos externos son coloreables por intervalo. [5]
Demostración: Sea c 1 una coloración de intervalo de 'G 1 ' tal que e=xy obtiene la etiqueta más pequeña entre las aristas incidentes a x e y . Tome c 1 (e)=0. Considere una coloración de intervalo c 1 de G 1 donde e obtiene la etiqueta más grande entre las aristas incidentes a x e y . Digamos, c 2 (e)=i . Luego construimos una coloración de intervalo c de G como c(e') = c 1 (e') si (e') ∈E(G 1 ) o c(e') = c 2 (e') - i si (e') ∈ E(G 1 ) .
Un grafo bipartito es (a, b)-biregular si cada vértice en una parte tiene grado a y cada vértice en la otra parte tiene grado b. Se ha conjeturado que todos estos grafos tienen coloraciones de intervalo. Hansen demostró que todo grafo bipartito G con ∆(G) ≤ 3 es coloreable por intervalo.
Se dice que una coloración de aristas de intervalo k de un grafo es una coloración de aristas de intervalo k equitativa si su conjunto de aristas E está dividido en K subconjuntos E 1 ,E 2 ,...,E k tales que E i es un conjunto independiente y la condición -1 ≤ E i ≤ E j ≤ 1 se cumple para todos los 1 ≤i ≤k,1 ≤j ≤k. El entero k más pequeño para el cual G es una coloración de aristas de intervalo equitativa se conoce como el número cromático equitativo de la coloración de aristas de intervalo de G y se denota por .
La coloración de bordes de intervalo tiene amplias aplicaciones en varios campos de la ciencia y la programación.
