Kolorowanie krawędzi interwału

W teorii grafów kolorowanie krawędzi przedziałów to rodzaj kolorowania krawędzi , w którym krawędzie są oznaczone liczbami całkowitymi w pewnym przedziale , każda liczba całkowita w przedziale jest używana przez co najmniej jedną krawędź, a w każdym wierzchołku etykiety, które pojawiają się na krawędziach padających, tworzą się kolejny zestaw różnych liczb.

Historia

Koncepcja kolejnego kolorowania krawędzi została wprowadzona wraz z terminologią „ interwałowego kolorowania krawędzi” przez Asratiana i Kamaliana w 1987 r. W ich artykule „Interwałowe kolorowanie krawędzi multigrafu”. Odkąd wprowadzono kolorowanie krawędzi interwałowych, matematycy badali istnienie wykresów z możliwością kolorowania krawędzi interwałowych, ponieważ nie wszystkie grafy pozwalają na kolorowanie krawędzi interwałowych. Prostą rodziną grafów, która pozwala na kolorowanie krawędzi przedziałów, jest graf pełny parzystego rzędu, a przeciwstawnym przykładem rodziny grafów są grafy kompletne nieparzystego rzędu. Najmniejszy graf, który nie pozwala na kolorowanie interwałowe. Odkryto nawet grafy z 28 wierzchołkami i maksymalnym stopniem 21, których Sevast'janov nie daje kolorować interwałowo, chociaż kolorowalność interwałowa grafów o maksymalnym stopniu leżącym między czwartym a dwunastym jest wciąż nieznana.

Asratyan i Kamalyan (1987) udowodnili, że jeśli graf można pokolorować interwałowo, to liczba chromatyczna krawędzi jest mniejsza lub równa jeden mniejsza niż liczba wierzchołków, a także zauważyli, że jeśli G jest r-regularny, to G ma kolorowanie interwałowe, jeśli i tylko wtedy, gdy G ma właściwe zabarwienie krawędzi r.

Kolorystyka krawędzi interwałów jest badana na grafach regularnych. grafy dwudzielne , które są regularne i nieregularne, grafy planarne, wśród innych rozszerzeń zapoczątkowanych w kolorowaniu krawędzi interwałowych.

Definicja

Niech G będzie prostym wykresem przedziałowym. Kolorowanie krawędzi grafu G kolorami 1, 2, . . . , t nazywa się ""kolorowaniem przedziału t"" jeśli dla każdego i ∈ {1, 2, . . . , t } istnieje co najmniej jedna krawędź G pokolorowana przez i , a kolory krawędzi padających na dowolny wierzchołek G są różne i tworzą przedział liczb całkowitych. Alternatywnie kolorowanie krawędzi interwału zdefiniowane jako: Kolorowanie krawędzi grafu G kolorami 1. . . t jest ' interwał t-colouring”, jeśli używane są wszystkie kolory, a kolory krawędzi padających na każdy wierzchołek G są różne i tworzą przedział liczb całkowitych. Wykres G jest „kolorowy w przedziale”, jeśli G ma kolorowanie w przedziale t dla pewnej dodatniej liczby całkowitej t . Niech N będzie zbiorem wszystkich kolorowych wykresów interwałowych. Dla wykresu G ∈ N , najmniejszą i największą wartość t , dla których G ma przedział t -kolorowanie, oznaczamy przez odpowiednio w ( G ) i W ( G ). Mówimy, że kolorowanie krawędzi interwałowych grafu jest równomiernym kolorowaniem krawędzi interwałowych, jeśli dowolne dwie klasy kolorów grafu różnią się co najwyżej o jeden.

Zbiór kolorów krawędzi incydentnych z wierzchołkiem (x) nazywamy widmem ( x ). Mówimy, że podzbiór R wierzchołków G ma właściwość i , jeśli istnieje odpowiednie t -kolorowanie krawędzi G , które jest przedziałem nad R .

Kilka wyników

Jeśli graf bez trójkątów G=(V,E) ma przedział t-kolorowania, to t ≤ |V|−1. Asratyan i Kamalian udowodnili, że jeśli G jest interwałowo kolorowalny, to χ'(G)=∆(G).

Petrosyan zbadał kolorowanie interwałowe pełnych grafów i n-wymiarowych sześcianów i wykazał, że jeśli n ≤ t ≤ n(n+1)/2, to n-wymiarowy sześcian Qn ma interwał t-kolorowania. Axenovich udowodnił, że wszystkie triangulacje płaszczyzny zewnętrznej z więcej niż trzema wierzchołkami i bez oddzielających trójkątów można pokolorować interwałowo. Jeśli G jest wykresem regularnym w(G)=∆(G) i G ma przedział t-kolorowania dla każdego t, w(G) ≤ t ≤ W(G).

Interwał 5-kolorowanie K ₆

Kolorowanie krawędzi interwałowych pełnego grafu

Graf kompletny jest interwałowo kolorowalny wtedy i tylko wtedy, gdy liczba jego wierzchołków jest parzysta.
Jeśli n= _p 2 ^q , gdzie p jest nieparzyste, q jest nieujemne, a 2n−1≤t≤4n−2−p−q, to pełny wykres K _2n ma przedział t-kolorowania.
Jeśli F jest zbiorem co najmniej n krawędzi incydentnych z jednym wierzchołkiem v pełnego grafu K _2n+1 , to K _2n+1 −F ma kolorowanie interwałowe.
Jeśli F jest maksymalnym dopasowaniem pełnego wykresu K _2n+1 z n≥2, to K _2n+1 −F nie ma kolorowania interwałowego.
Jeśli n ≤ t ≤ ${\ Displaystyle {\ Frac {n (n + 1)}} {2}}}$ , to n-wymiarowy sześcian Qn ma przedział t-kolorowania.

Kolorowanie krawędzi interwałowych grafów dwudzielnych

Dla dowolnego m, n ∈ N, pełny graf dwudzielny K _m,n jest interwałowo kolorowalny i

(1) w ( K _m,n ) = m + n − gcd(m, n),

(2) W ( K. _m,n ) = m + n − 1,

(3) jeśli w ( K _m,n ) ≤ t ≤ W ( K _m,n ), to K _m,n ma przedział t-kolorowania.

Jeśli G jest grafem dwudzielnym, to χ′(G) = ∆(G).
Jeśli G ∈ N, to G[ K _m,n ] ∈ N dla dowolnego m, n ∈ N. Co więcej, dla dowolnego m, n ∈ N, mamy

w (G[ Km _,n ]) ≤ (w(G) + 1)(m + n) − 1 i W (G[ Km _,n ]) ≥ (W(G) + 1)(m + n ) − 1.

Jeśli G jest spójnym grafem dwudzielnym i G ∈ N, to W(G) ≤ diam(G) (∆(G) − 1) + 1.

Kolorowanie krawędzi interwałowych grafów planarnych

Przedziałowe kolorowanie krawędzi grafów płaszczyzny zewnętrznej zostało zbadane przez Giaro i Kubale i udowodniło, że wszystkie grafy dwudzielne płaszczyzny zewnętrznej można kolorować interwałowo.

Jeśli G = G ₁ eG ₂ gdzie G ₁ i G ₂ mają kolorystykę interwałową, w której e ma etykietę zewnętrzną. Wtedy G ma kolorowanie interwałowe.

Dowód: Niech c ₁ będzie kolorowaniem przedziałowym 'G ₁ ' takim, że e=xy otrzyma najmniejszą etykietę spośród krawędzi incydentnych z x i y . Weźmy c ₁ (e)=0. Rozważmy kolorowanie przedziału c ₁ z G ₁ , gdzie e otrzymuje największą etykietę spośród krawędzi incydentnych z x i y . Powiedzmy, c ₂ (e) = i . Następnie konstruujemy przedział kolorowania c z G jako c(e') = c ₁ (e') jeśli (e') ∈E(G ₁ ) lub c(e') = c ₂ (e') - i jeśli (e') ∈ E(G ₁ ) .

Jeśli G jest grafem płaszczyzny zewnętrznej rzędu co najmniej 4 bez oddzielających trójkątów, to ma kolorowanie interwałowe.
Niech G będzie grafem otrzymanym przez usunięcie niektórych dzielących krawędzi pod pewnym przedziałem kolorowania grafu H . Wtedy G jest interwałem kolorowalnym.
niech H będzie triangulacją płaszczyzny zewnętrznej bez oddzielnych trójkątów i niech H = H ₁ ,----- H _m będzie dekompozycją z łączącymi się krawędziami e ₁ ,----, e _m-1 .Jeśli G otrzymujemy z H przez usunięcie jakieś krawędzie łączące, to G ma kolorowanie interwałowe.
Dla dowolnego kolorowalnego wykresu interwałowego G na n wierzchołkach t(G) ≤(11/6) n .

Interwałowe kolorowanie krawędzi dwuregularnych grafów dwudzielnych o małych stopniach wierzchołków

Graf dwudzielny jest (a, b)-dwuregularny, jeśli każdy wierzchołek w jednej części ma stopień a, a każdy wierzchołek w drugiej części ma stopień b. Przypuszczano, że wszystkie takie wykresy mają kolorowanie interwałowe. Hansen udowodnił, że każdy graf dwudzielny G z ∆(G) ≤ 3 można pokolorować interwałowo.

Wyrównane kolorowanie krawędzi K-interwału

Mówimy, że kolorowanie krawędzi grafu w przedziale k jest równe kolorowaniu krawędzi w przedziale k, jeśli jego zbiór krawędzi E jest podzielony na K podzbiorów E ₁ , E ₂ ,...,E _k takich, że E _i jest zbiorem niezależnym i warunek -1 ≤ E _i ≤ E _j ≤ 1 zachodzi dla wszystkich 1 ≤i ≤k,1 ≤j ≤k. Najmniejsza liczba całkowita k, dla której G jest równomiernym zabarwieniem krawędzi przedziału, jest znana jako równoważna liczba chromatyczna zabarwienia krawędzi przedziału G i jest oznaczana przez ${\ Displaystyle \ chi _ {eie} (G)}$ .

Aplikacje

Interwałowe kolorowanie krawędzi ma szerokie zastosowanie w różnych dziedzinach nauki i planowania.

Jednym z podstawowych zastosowań kolorowania krawędzi interwałowych jest planowanie harmonogramu zajęć bez kolizji, w tej aplikacji godziny lekcyjne stają się wierzchołkami i dzielą one krawędź, jeśli oba mają wspólny przedział czasowy. Liczba kolorów potrzebnych do pokolorowania krawędzi to liczba zajęć potrzebnych do prowadzenia zajęć bez kolizji. Jest to stosowane we wszystkich przypadkach, gdy trzeba zorganizować dwa lub więcej wydarzeń, aby uniknąć kolizji.
Podobne zastosowanie znajduje się w harmonogramowaniu czasu pracy procesorów. Np. harmonogramowanie przesyłania plików w sieci rozproszonej lub planowanie testów diagnostycznych w systemie wielokomputerowym, a także szeregowanie zadań w systemie otwartego sklepu. Opracowywane są różne algorytmy dla ten cel.
Możliwość kolorowania krawędzi interwałowych kompletnych wykresów pomaga w zaplanowaniu 2n gier w turnieju, tak aby każda drużyna grała ze sobą.
Badanie możliwości kolorowania krawędzi interwałowych grafów planarnych i grafów dwudzielnych rodzi wiele innych zastosowań.

przypuszczenia

Dla dowolnego m,n∈N, K1,m,n ∈ N wtedy i tylko wtedy, gdy gcd(m+1, n+1) = 1.
Jeśli G jest grafem planarnym na n wierzchołkach, to maksymalna liczba kolorów użytych w kolorowaniu interwałowym G wynosi co najwyżej (3/2) n .
Wykres płaszczyzny zewnętrznej uzyskany z triangulacji płaszczyzny zewnętrznej bez oddzielających trójkątów przez usunięcie krawędzi wewnętrznych można pokolorować interwałowo.

Zobacz też