Colorarea marginilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 septembrie 2022; verificarea necesită 1 editare .

Colorarea marginilor este alocarea de „culori” la marginile unui grafic astfel încât să nu aibă două margini adiacente aceeași culoare. Colorarea marginilor este unul dintre diferitele tipuri de colorare a graficelor. Problema de colorare a marginilor întreabă dacă este posibil să colorezi muchiile unui grafic dat cu cel mult culori diferite pentru o anumită valoare sau pentru un număr minim posibil de culori. Numărul minim de culori necesare pentru a colora marginile unui grafic dat se numește indicele cromatic al graficului. De exemplu, marginile graficului din ilustrație pot fi colorate cu trei culori, dar nu pot fi colorate cu două, deci graficul are un indice cromatic de 3. $k$ $k$

Conform teoremei lui Vizing , numărul de culori necesare pentru colorarea muchiilor unui grafic simplu este fie egal cu gradul maxim de vârfuri , fie . Pentru unele grafice, cum ar fi graficele bipartite și graficele plane de grad înalt , numărul de culori este întotdeauna , în timp ce pentru multigrafe , numărul de culori poate fi de până la . Există algoritmi de timp polinomial care produc o colorare optimă a graficelor bipartite și o colorare a unui grafic simplu non-bipartit cu un număr de culori . Cu toate acestea, în cazul general, problema găsirii colorării optime a liniei este NP-completă , iar cel mai rapid algoritm cunoscut pentru aceasta rulează în timp exponențial. Au fost studiate multe variante ale problemei de colorare a marginilor, în care condițiile de atribuire a unei culori unei margini trebuie să îndeplinească alte condiții decât conjugarea. Problemele de colorare a marginilor au aplicații în probleme de programare și atribuire a frecvenței în rețelele de fibră optică . $\Delta$ $\Delta +1$ $\Delta$ $3{\Delta }/2$ ${\Delta }+1$

Exemple

Graficul-ciclu poate fi colorat în 2 culori dacă lungimea ciclului este uniformă - utilizați doar 2 culori pe rând, trecând secvențial marginile ciclului. Totuși, în cazul unei lungimi impare, sunt necesare 3 culori [1] .

Marginile unui grafic complet cu vârfuri pot fi codificate cu culori dacă sunt egale. Acesta este un caz special al teoremei lui Baranyai . Soifer [2] dă următoarea construcție geometrică a colorării în acest caz: plasăm puncte în colțurile și în centrul unui -gon regulat. Pentru fiecare clasă de culoare, selectăm o muchie care conectează centrul și unul dintre vârfurile poligonului și toate muchiile perpendiculare pe aceasta, conectând perechi de vârfuri poligonului. Cu toate acestea, dacă sunt impare, culorile sunt necesare - fiecare culoare poate fi folosită doar pentru a colora marginile, partea --a a tuturor marginilor [3] . $K_n$ $n$ $n-1$ $n$ $n$ $(n-1)$ $n$ $n$ $(n-1)/2$ $1/n$

Unii autori au studiat colorarea marginilor graficelor impare , -grafice obișnuite în care vârfurile reprezintă echipe de jucători dintr-un număr total de jucători și în care marginile reprezintă posibile perechi ale acestor echipe (cu un jucător în ofsaid de arbitru). În cazul în care obținem binecunoscutul graf Petersen . După cum explică Biggs $n$ $(n-1)$ $2n-1$ $n=3$ [4] , problema (pentru) este că jucătorii doresc să găsească un program astfel încât echipele să joace fiecare dintre cele șase jocuri în zile diferite ale săptămânii, excluzând duminica pentru toți jucătorii. În formularea matematică, ei doresc să găsească o linie de colorare cu 6 culori a graficelor obișnuite. Când esteegală cu 3, 4 sau 8, colorarea liniei graficuluinecesităculori, dar pentru 5, 6 și 7, sunt necesare doarculori [5] . $n=6$ $O_{6}$ $n$ $Pe}$ $n+1$ $n$

Definiții

Ca și în cazul colorării vârfurilor , colorarea muchiilor unui grafic, dacă nu este specificat în mod explicit altfel, presupune întotdeauna că două muchii adiacente au culori diferite. Două muchii sunt considerate adiacente dacă au un vârf comun. O colorare a muchiei unui grafic poate fi considerată echivalentul unei colorări a vârfurilor a unui grafic cu linii , un grafic care are un vârf pentru fiecare muchie a graficului și o muchie pentru fiecare pereche de muchii adiacente . $G$ $L(G)$ $G$ $G$

O colorare adecvată cu diferite culori se numește o colorare a marginilor (corespunzătoare) . Dacă pentru un grafic poate fi găsită o colorare (corespunzătoare) a muchiilor , se spune că este colorabilă a muchiilor . Cel mai mic număr de culori necesare pentru o colorare a liniilor (corecte) a unui grafic se numește indice cromatic sau număr cromatic de margine . Indicele cromatic este uneori scris ca . În această notație, indexul indică faptul că marginile sunt obiecte unidimensionale. Un grafic este colorat cu muchia dacă indicele cromatic este exact . Indicele cromatic nu trebuie confundat cu numărul cromatic sau cu numărul minim de culori necesare pentru a colora corect vârfurile unui grafic . $k$ $k$ $k$ $k$ $G$ $\chi {\prime }(G)$ $\chi _{1}(G)$ $k$ $k$ $\chi (G)$ $\chi _{0}(G)$ $G$

Dacă nu se specifică altfel, toate graficele sunt presupuse a fi simple, spre deosebire de multigrafele , în care două sau mai multe muchii pot conecta aceeași pereche de vârfuri și în care pot exista bucle (o muchie ale cărei vârfuri de capăt sunt aceleași). Pentru majoritatea problemelor de colorare a liniilor, graficele simple se comportă diferit de multigrafe și este necesară o atenție suplimentară atunci când extindeți teoremele de colorare a liniilor de la grafice simple la multigrafe.

Relația cu potrivirile

O potrivire într-un grafic este un set de muchii dintre care două nu sunt adiacente. O potrivire se numește perfectă dacă muchiile sale conțin toate vârfurile graficului și maximă dacă conține numărul maxim posibil de muchii. Într-o colorare a marginilor, marginile de aceeași culoare trebuie să fie neadiacente, deci formează o potrivire. Astfel, o colorare adecvată a marginilor este aceeași cu descompunerea unui grafic în potriviri disjunctive. $G$

Dacă dimensiunea potrivirii maxime într-un grafic dat este mică, este necesar un număr mare de potriviri pentru a acoperi toate marginile graficului. Mai formal, această explicație presupune că, dacă un grafic are muchii și dacă maximum de muchii pot aparține unei potriviri maxime, atunci fiecare colorare a muchiei graficului trebuie să conțină cel puțin culori distincte. [6] De exemplu, graficul planar cu 16 vârfuri prezentat în ilustrație are muchii. Nu există o potrivire perfectă în acest grafic - dacă vârful central aparține potrivirii, vârfurile rămase pot fi împărțite în trei grupuri conectate cu numărul de vârfuri 4, 5, 5. Subgrafele rezultate cu un număr impar de vârfuri nu au o potrivire perfectă. Cu toate acestea, graficul are o potrivire maximă cu șapte muchii, deci . Prin urmare, numărul de culori necesar pentru o colorare a muchiei unui grafic este de cel puțin 24/7 și, deoarece numărul de culori trebuie să fie un întreg, obținem cel puțin 4 culori. $m$ $\beta$ $m/\beta$ $m=24$ $\beta=7$

Pentru graficele obișnuite de grade care nu se potrivesc perfect, această limită inferioară poate fi utilizată pentru a arăta că sunt necesare cel puțin culori. [6] În special, acest lucru este valabil pentru graficele obișnuite cu un număr impar de vârfuri. Pentru astfel de grafice, după lema strângerii de mână , , la rândul său, trebuie să fie par . Cu toate acestea, inegalitatea nu explică pe deplin indicele cromatic al unui graf obișnuit arbitrar, deoarece există grafuri regulate care au o potrivire perfectă, dar nu sunt colorabile cu muchia k . De exemplu, graficul Petersen este obișnuit cu și cu muchii într-o potrivire perfectă, dar nu are o culoare cu trei margini. $k$ $k+1$ $k$ $\chi {\prime }\geqslant m\beta$ $m=15$ $\beta=5$

Relația cu gradul

Teorema lui Vizing

Numărul cromatic al muchiei unui grafic este strâns legat de gradul maxim (numărul maxim de muchii adiacente oricărui vârf al graficului ). Este clar că , deci, dacă diferite margini conțin un vârf , atunci toate aceste margini trebuie colorate cu culori diferite, ceea ce este posibil doar dacă există cel puțin culori. Teorema lui Vizing (numită după Vadim Vizing , care a publicat-o în 1964) afirmă că această limită este aproape exactă - pentru orice grafic, numărul cromatic la muchie este fie , fie . Dacă , se spune că G este din clasa 1, în caz contrar se spune că este din clasa 2. $G$ ${\Delta }(G)$ $G$ $\chi {\prime }(G)\geq {\Delta }(G)$ ${\Delta }$ $v$ $\Delta$ ${\Delta }(G)$ $\Delta (G)+1$ $\chi {\prime }(G)={\Delta }(G)$

Orice graf bipartit are clasa 1 [7] și aproape toate grafurile aleatoare au clasa 1 [8] . Totuși, problema verificării dacă un graf arbitrar are clasa 1 este o problemă NP-completă [9] .

Vizing [10] a demonstrat că grafurile plane de gradul maxim cel puțin opt au clasa 1 și a presupus că același lucru este valabil și pentru grafurile plane de gradul 7 sau 6. Pe de altă parte, există grafuri plane cu gradul maxim între doi și cinci care au clasa 2. De atunci, conjectura a fost dovedită pentru șapte [11] . Grafice plane fără punți Graficele cubice au clasa 1, iar aceasta este echivalentă cu formularea problemei cu patru culori [12] .

Grafice obișnuite

Factorizarea 1 a unui grafic k - regulat , adică descompunerea muchiilor graficului în potriviri perfecte , este aceeași cu colorarea k -muchii a graficului. Astfel, un grafic obișnuit are o factorizare 1 dacă și numai dacă are clasa 1. Un caz special, colorarea liniilor cu 3 culori a graficelor cubice (3-regulate) este uneori numită colorarea Tite .

Nu orice grafic obișnuit are o factorizare 1. De exemplu, Graf Petersen nu. Snark-urile sunt definite ca grafice care, ca și graficul Petersen, sunt fără punte, 3-regulate și de clasa 2.

Conform teoremei lui Koenig [7] , orice graf regulat bipartit are o factorizare 1. Teorema a fost formulată mai devreme în termeni de configurații proiective și demonstrată de Ernst Steinitz .

Multigrafe

Pentru multigrafe , în care mai multe muchii pot conecta aceleași două vârfuri, rezultate similare, dar mai slabe sunt cunoscute teoremei lui Wizing privind numărul cromatic al muchiei , gradul maxim și multiplicitatea , numărul maxim de muchii dintr-un mănunchi de muchii paralele (adică având același vârfuri de capăt). Ca un exemplu simplu care arată că teorema lui Vizing nu se generalizează la multigrafe, luați în considerare multigraful Shannon , un multigraf cu trei vârfuri și trei mănunchiuri de muchii paralele care conectează fiecare pereche de vârfuri. În acest exemplu: - fiecare vârf este adiacent doar la două dintre cele trei mănunchiuri de muchii paralele, dar numărul cromatic al muchiei este (în graficul muchiei , oricare două muchii sunt adiacente, deci toate muchiile trebuie să fie colorate în culori diferite). Într-o lucrare inspirată de teorema lui Vizing, Soifer și Shannon [13] [14] au arătat că acesta este cel mai rău caz pentru orice multigraf . În plus, pentru orice multigraf . Această inegalitate se reduce la teorema lui Vizing pentru grafice simple (pentru ei ). $\chi {\prime }(G)$ $\Delta (G)$ $\mu (G)$ $\mu (G)$ $\Delta (G)=2\mu (G)$ $\mu (G)$ $3\mu (G)$ $3\mu (G)$ $\chi {\prime }(G)\leq (3/2)\Delta (G)$ $G$ $G$ $\chi {\prime }(G)\leq \Delta (G)+\mu (G)$ $\mu (G)=1$

Algoritmi

Deoarece problema verificării dacă un graf are clasa 1 este NP-complet , nu există un algoritm de colorare a liniilor de timp polinomial cunoscut pentru orice graf care oferă o colorare optimă. Totuși, au fost dezvoltați o serie de algoritmi care slăbesc unul sau mai multe criterii: aceștia lucrează pe un subset de grafice, sau nu dau întotdeauna numărul optim de culori, sau nu funcționează întotdeauna în timp polinomial.

Colorarea optimă a unor clase speciale de grafice

În cazul grafurilor bipartite sau multigrafelor cu grad maxim , numărul optim de culori este exact . Sa arătat în 2001 [15] că colorarea optimă a liniilor acestor grafice poate fi găsită în timp aproape liniar , unde este numărul de muchii din grafic. Algoritmi mai simpli, dar ceva mai lenți au fost descriși anterior de Cole și Hopcroft [16] și Alon [17] . Algoritmul lui Alon începe prin a face ca graficul să fie regulat, fără o mare creștere a gradului sau a mărimii mult, prin îmbinarea perechilor de vârfuri care aparțin aceleiași părți a graficului bipartit și apoi adăugând un număr mic de vârfuri și muchii. După aceea, dacă gradul este impar, Alon găsește o potrivire perfectă în timp liniar, îi atribuie o culoare și o elimină din grafic, rezultând un grafic de grad par. În cele din urmă, Alon folosește observația lui Gabov [18] că alegerea submulților alternante de muchii în ciclul Euler al unui graf îl împarte în două subgrafe regulate, transformând problema de colorare a muchiilor în două probleme mai mici, astfel încât algoritmul său rezolvă acum aceste două subprobleme în mod recursiv . Timpul total de rulare al algoritmului este estimat ca . $\Delta$ $\Delta$ $O(m\,\log\Delta )$ $m$ $O(m\,\log m)$

Pentru graficele plane cu grad maxim , numărul optim de culori este din nou exact . Sub o ipoteză mai strictă că , se poate găsi colorarea optimă a marginilor în timp liniar [19] . ${\Delta }\geq 7$ $\Delta$ ${\Delta }\geq 9$

Algoritmi care folosesc mai multe culori decât este necesar pentru o colorare optimă

Există algoritmi în timp polinomial pentru colorarea oricărui grafic cu culori, ceea ce corespunde limitei date de teorema lui Vizing [20] [21] . $\Delta +1$

Pentru multigrafe în 1987 [22] există următorul algoritm (atribuit lui Eli Upfal ): multigraful original se face Euler prin adăugarea unui vârf legat prin muchii la toate vârfurile de grad impar; se găsește calea lui Euler, se alege orientarea pentru această cale; se creează un graf bipartit care conține două copii ale fiecărui vârf al grafului , câte una în fiecare parte, și muchii de la un vârf din partea stângă la un vârf din partea dreaptă, când o cale direcționată are un arc de la până la în grafic . Apoi, aplicăm algoritmul de colorare a muchiei grafului bipartit pentru graf . Fiecare culoare în corespunde unui set de muchii în , care formează un subgraf cu gradul maxim doi, adică o unire disjunctă de trasee și cicluri astfel încât pentru fiecare culoare în , se pot forma trei culori în . Timpul de rulare al algoritmului este limitat de timpul colorării unui graf bipartit folosind algoritmul lui Cole, Ost și Schirr [15] . Numărul de culori pe care le folosește acest algoritm nu depășește , care este aproape, dar nu chiar la fel cu, limita lui Shannon . Același lucru se poate face direct cu un algoritm paralel . În același articol, Karloff și Schmois propun, de asemenea, un algoritm de timp liniar pentru colorarea multigrafelor de cel mult gradul trei cu patru culori (care satisface atât limita Shannon, cât și limita Weezing). Acest algoritm funcționează pe principii similare - algoritmul adaugă și un vârf pentru a face graficul eulerian, găsește o cale Euler și apoi selectează seturi alternative de muchii în cale pentru a împărți graficul în două subseturi de gradul doi maxim. Căile și chiar ciclurile fiecărui subset pot fi colorate în două culori (două culori pe subgraf). Următorul pas este colorarea marginilor ciclurilor impare în care cel puțin o margine poate fi colorată cu una dintre cele două culori aparținând subgrafului opus. Eliminarea acestei margini din ciclul impar lasă o cale care poate fi colorată cu două culori. $G$ $H$ $G$ $u$ $v$ $u$ $v$ $G$ $H$ $H$ $G$ $H$ $G$ $O(m\,\log\Delta )$ $3\left\lceil {\frac {\Delta }2}\right\rceil$ $\left\lfloor {\frac {3\Delta }2}\right\rfloor$

Un algoritm de colorare lacom care selectează secvenţial marginile unui grafic sau multigraf şi atribuie prima culoare validă poate folosi uneori culori care pot fi aproape de două ori numărul necesar de culori. Cu toate acestea, are avantajul că poate fi folosit în algoritmi online care nu știu nimic despre structura graficului în avans. În aceste condiții, coeficientul său competitiv este egal cu doi, iar acest coeficient este optim - niciun alt algoritm nu poate oferi indicatori mai buni [23] . Totuși, dacă muchiile ajung în ordine aleatorie și graficul original are cel puțin un grad logaritmic, se poate obține un coeficient competitiv mai mic [24] . $2{\Delta }-1$

Unii autori au emis ipoteza că indicele cromatic fracționar al oricărui multigraf (un număr care poate fi calculat în timp polinomial folosind programarea liniară ) diferă de indicele cromatic cu nu mai mult de unu [25] . Dacă presupunerea este corectă, se va putea găsi un număr care nu diferă de indicele cromatic cu mai mult de unul în cazul multigrafelor, ceea ce corespunde teoremei lui Vizing pentru graficele simple. Deși, în cazul general, presupunerea nu a fost dovedită, se știe că este adevărat dacă indicele cromatic nu este mai mic decât , la fel ca în cazul multigrafelor cu multiplicitate suficient de mare [26] . ${\Delta }+{\sqrt {{\Delta }/2))$

Algoritmi exacti

Este ușor să verificați dacă un grafic poate fi colorat cu margini cu una sau două culori, astfel încât primul caz non-trivial de colorare este verificarea dacă un grafic poate fi colorat cu margini cu trei culori. În 2009 [27] , sa demonstrat că este posibil să se verifice dacă există o colorare a muchiei unui grafic cu trei culori în timp folosind doar un spațiu polinomial. Deși aceste limite de timp sunt exponențiale, este substanțial mai rapid decât algoritmul de căutare cu forță brută, luând în considerare toate colorațiile de margine posibile. Orice grafic cu 3 vârfuri regulate conectat dublu are colorări cu 3 muchii. Și toate pot fi listate în timp (puțin mai lent decât timpul de căutare a unei singure colorări). După cum a observat Kuperberg , graficul unei prisme peste un -gon are multe colorări, ceea ce arată că această legătură este exactă [28] . $O(1,344^{n})$ $n$ $O(2^{{n/2}})$ $O(2^{{n/2}})$ $n/2$

Prin aplicarea unor algoritmi exacti de colorare a nodurilor unui grafic cu linii , se poate colora în mod optim orice grafic cu muchii, indiferent de numărul de culori necesare, în timp folosind spațiu exponențial, sau în timp și spațiu polinomial [29] . $m$ $2^{m}m^{{O(1)}}$ $O(2,2461^{m})$

Deoarece problema de colorare a marginilor este NP-complet chiar și pentru trei culori, este puțin probabil să se preteze la o parametrizare fixă în funcție de numărul de culori. Cu toate acestea, sarcina se pretează la parametrizare prin alți parametri. În special, Zhou, Nakano și Nishiseki [30] au arătat că pentru graficele cu lățimea arborelui, colorarea optimă a liniei poate fi găsită în timp , care crește exponențial de la , dar numai liniar de la numărul de vârfuri ale graficului . $w$ $O(nw(6w)^{{w(w+1)/2}})$ $w$ $n$

În 1991 [31] , problema de colorare a muchiilor a fost formulată ca o problemă de programare cu numere întregi și au fost efectuate experimente folosind pachete de programare cu numere întregi pentru colorarea muchiilor graficelor, dar nu a fost oferită nicio analiză a complexității unor astfel de algoritmi.

Proprietăți suplimentare

Un grafic este colorabil în mod unic pentru margini dacă și numai dacă există o singură modalitate de a împărți marginile în clase de culoare, fără a număra posibilele permutări de culori. Pentru graficele care pot fi colorate în mod unic pentru margini sunt doar căi, cicluri și stele , dar pentru alte grafice pot fi colorate în mod unic pentru margini. Orice grafic unic colorabil cu 3 muchii are exact trei cicluri hamiltoniene (formate prin eliminarea uneia dintre cele trei culori), dar există grafice cu 3 laturi obișnuite care au trei cicluri hamiltoniene, dar nu au o colorare unică cu 3 muchii, cum ar fi grafice Petersen generalizate pentru . Se cunoaște un singur graf neplanar, unic cu 3 muchii colorabile, acesta este graful Petersen generalizat și există o presupunere că nu există altele [32] . $k$ $k$ $k!$ $k\neq 3$ $k$ $k = 3$ $k$ $G(6n+3,2)$ $n\geq 2$ $G(9,2)$

Folkman și Fulkerson [33] au studiat șiruri de numere necrescătoare pentru care există o colorare a muchiei unui grafic dat cu muchii ale primei culori, muchii ale celei de-a doua culori și așa mai departe. Ei au observat că dacă o secvență se potrivește în sensul descris și dacă este mai mare din punct de vedere lexicografic decât o secvență cu aceeași sumă, atunci se potrivește. Dacă din punct de vedere lexicografic, poate fi convertit în pas cu pas, scăzând unul dintre numere cu câte unul la fiecare pas și crescând numărul următor ( ) cu unul. În ceea ce privește colorarea marginilor, începem cu colorarea , apoi schimbăm secvențial culoarea și în lanțul Kempe , cea mai lungă cale de margini alternând două culori. În special, orice grafic are o linie de colorare corectă , o colorare a marginilor cu un număr optim de culori în care două clase de culori diferă ca mărime cu cel mult una. $m_{1},m_{2},m_{3},...$ $G$ $m_1$ $m_2$ $P$ $Q$ $Q$ $P>Q$ $P$ $Q$ $m_i$ $m_{j}$ $i<j$ $P$ $i$ $j$

Teorema lui de Bruijn-Erdős poate fi folosită pentru a extinde multe proprietăți ale colorării liniilor de la grafice finite la infinite . De exemplu, teoremele lui Shannon și Vizing privind relația dintre gradul unui graf și indicele său cromatic sunt ambele generalizate cu ușurință la grafuri infinite [34] .

În 2011 [35] , a fost luată în considerare problema găsirii unei imagini a unui grafic cubic dat cu proprietățile că toate muchiile din imagine au unul dintre cele trei unghiuri de pantă diferite și nici două muchii nu se află pe aceeași linie. Dacă există o astfel de reprezentare a graficului din figură, este clar că unghiul de înclinare al marginilor poate fi considerat culoarea marginilor într-o colorare în trei culori a graficului. De exemplu, modelul muchiilor și diagonalelor lungi ale unui hexagon obișnuit reprezintă o colorare cu 3 margini a unui grafic în acest fel. Se arată că un graf bipartit cu 3 obișnuiți cu o colorare Tite dată are o reprezentare grafică a acestei forme dacă și numai dacă este conectat la k-edge . Pentru graficele non-bipartite, condiția este puțin mai complicată - o colorare dată poate fi reprezentată printr-un astfel de model dacă capacul bipartit dublu al graficului este conectat cu 3 muchii și dacă îndepărtarea a două muchii egale colorate duce la un non-bipartit. subgraf. Toate aceste condiții sunt ușor de verificat în timp polinomial, totuși, problema verificării dacă un grafic cu 4 laturi cu 4 laturi regulate are un model cu patru pante corespunzătoare culorilor este completă pentru teoria existenței numerelor reale , a aceeași clasă de complexitate ca NP-completitudine. $K_{{3,3}}$

Având o legătură cu gradul maxim și numărul maxim de potriviri ale unui grafic, indicele cromatic este, de asemenea, strâns legat de caracterul arborescent al graficului , numărul minim de păduri liniare (uniunea disjunsă de căi) în care marginile graficului. poate fi compartimentat. Potrivirea este un tip special de pădure liniară, dar, pe de altă parte, orice pădure liniară poate fi colorată cu două margini, deci pentru orice . Conjectura lui Akiyama afirmă că , ceea ce ar implica o inegalitate mai puternică . Pentru graficele de grad maxim, trei este întotdeauna exact egal cu doi, deci constrângerea corespunde graniței care urmează din teorema lui Vizing [36] . $la(G)$ $G$ $G$ $la(G)\leq \chi {\prime }(G)\leq 2la(G)$ ${\mathop {{\mathrm {la}}}}(G)\leq \left\lceil {\frac {{\Delta }+1}{2}}\right\rceil$ $2la(G)-2\leq \chi {\prime }(G)\leq 2la(G)$ $la(G)$ $\chi {\prime }(G)\leq 2la(G)$

Alte tipuri de colorare a marginilor

Numărul Thue al graficului este numărul de culori necesare pentru o colorare a marginilor care satisface o cerință mai puternică decât orice cale de lungime egală, și anume că prima și a doua jumătate a căii trebuie să formeze secvențe diferite de culori.

Treenessul unui grafic este numărul minim de culori necesare pentru a colora astfel încât marginile oricărei culori să nu conțină cicluri (și nu, ca în problema standard de colorare, marginile aceleiași culori să nu fie adiacente). Astfel, acesta este numărul minim de elemente ale pădurii în care pot fi descompuse marginile graficului [37] . Spre deosebire de numărul cromatic, lățimea pădurii poate fi calculată în timp polinomial [38] .

Problema colorării muchiilor prescrise este o problemă în care, pentru un grafic dat, pentru fiecare arc din care este dată o listă de culori, este necesar să se găsească o colorare a marginilor potrivită, în care fiecare culoare să fie luată dintr-un lista dată. Indicele cromatic prescris al unui grafic este cel mai mic numărpentru care, indiferent de alegerea listelor de culori ale muchiei, dacă fiecărei muchii îi sunt date cel puținculori, este garantată existența unei colorări. Indicele cromatic prescris nu este întotdeauna mai mic decât numărul cromatic. Conjectura lui Dinitz despre umplerea pătratelor latine parțiale poate fi reformulată ca afirmația că numărul cromatic de muchie prescris al unui graf bipartit complet este egal cu numărul cromatic de muchie. În 1995 [39] , conjectura a fost rezolvată și s-a dovedit o afirmație mai puternică că pentru orice graf bipartit, indicele cromatic și indicele cromatic prescris sunt egale. O presupunere și mai generală este formulată despre egalitatea numărului cromatic și a numărului cromatic prescris pentru multigrafe arbitrare fără bucle. Această ipoteză rămâne deschisă. $G$ $k$ $k$ $K_{{n,n}}$ $n$

Multe variații ale problemei de colorare a vârfurilor care au fost studiate au fost extinse la colorarea marginilor. De exemplu, problema de colorare a marginii întregi este o variantă a colorării complete , colorarea corectă a vârfurilor, în care orice pereche de culori trebuie să fie prezentă cel puțin o dată în setul de vârfuri conjugate, iar problema este de a maximiza numărul total de vârfuri. culori [40] . Colorarea strictă a marginilor este o variantă a colorării stricte a marginilor , în care orice două muchii cu vârfuri de capăt adiacente trebuie să aibă culori diferite [41] . Colorarea strictă a marginilor este utilizată în aspectul canalului pentru rețelele fără fir [42] . O colorare a liniei aciclice este o variantă a unei colorări aciclice în care orice două culori formează un subgraf aciclic (adică o pădure) [43] .

În 2008 [28] , a fost studiată o colorare pe 3 linii a graficelor cubice cu proprietatea suplimentară că două cicluri cu două culori nu au mai mult de o margine comună; în special, s-a demonstrat că existența unei astfel de colorări este echivalentă cu existența unui grafic desenat pe o rețea de numere întregi tridimensionale cu muchii pe linii, paralele cu axele de coordonate, iar fiecare astfel de linie conține cel mult două vârfuri. Cu toate acestea, ca și în cazul problemei standard de colorare cu 3 margini, găsirea unei colorări de acest tip este o problemă NP-completă.

Colorarea totală este un tip de colorare care combină colorarea vârfurilor și a marginilor, în care atât vârfurile, cât și marginile sunt colorate. Orice vârf și muchia căreia se află la capăt sau două muchii adiacente trebuie să aibă culori diferite, precum și două vârfuri adiacente. Există o presupunere (combinând teorema lui Vizing și teorema lui Brooks ) că orice grafic are o colorare totală în care numărul de culori nu depășește puterea maximă plus două. Ipoteza nu a fost dovedită.

Dacă un grafic cu 3 obișnuiți pe o suprafață este colorabil cu 3 muchii, graficul său dual formează o triangulare a suprafeței, care este, de asemenea, colorabilă cu marginile (deși, în general, colorarea liniilor nu este corectă) în sensul că fiecare triunghiul este colorat cu trei culori, o margine pe culoare. Alte colorări și orientări ale triunghiurilor, împreună cu alte constrângeri locale asupra modului în care culorile sunt distribuite peste vârfurile sau fețele unei triunghiuri, pot fi utilizate pentru a codifica anumite tipuri de obiecte geometrice. De exemplu, subdiviziunile dreptunghiulare (părți ale unei partiții dreptunghiulare a unui dreptunghi în dreptunghiuri mai mici, unde trei dreptunghiuri se întâlnesc în fiecare punct) pot fi descrise combinatoriu prin „marcare regulată”, o colorare în două culori a marginilor unui grafic de triangulație dual cu o subdiviziune dreptunghiulară, cu constrângerea ca muchiile adiacente fiecărui vârf să formeze patru grupuri de muchii mergând (în sensul acelor de ceasornic) într-un rând. În cadrul fiecărui grup, marginile sunt vopsite în aceeași culoare și au aceeași direcție. Acest marcaj este dual cu colorarea rafinamentului în sine, în care marginile verticale au o culoare, iar marginile orizontale alta. Constrângeri locale similare de ordinea muchiilor colorate pentru un vârf pot fi utilizate pentru a codifica încorporarea graficelor plane într-o grilă formată din linii drepte și poliedre 3D cu fețe paralele cu planurile de coordonate. Pentru fiecare dintre aceste trei tipuri de marcaje regulate, setul de marcaje regulate formează o rețea distributivă , care poate fi folosită pentru a enumera rapid toate structurile geometrice pe baza aceluiași grafic, sau pentru a găsi o structură care să satisfacă constrângeri suplimentare [44] .

Un automat finit determinist poate fi reprezentat ca un grafic direcționat în care fiecare vârf are același grad exterior de vârfuri și în care muchiile sunt colorate în așa fel încât oricare două muchii cu același vârf de început să aibă culori diferite. Problema de colorare a drumului este o problemă de colorare a liniilor pentru un grafic direcționat cu același grad exterior, astfel încât automatul rezultat are un cuvânt de sincronizare . Trachtman ( Trachtman 2009 ) a rezolvat problema colorării drumurilor demonstrând că o astfel de colorare poate fi găsită dacă graficul dat este puternic conectat și aperiodic . $d$

Teorema lui Ramsey se referă la problema colorării muchiilor unui graf complet mare pentru a evita crearea de subgrafe complete monocromatice de o anumită dimensiune . Conform teoremei, există un număr astfel încât pentru colorarea specificată este imposibilă. De exemplu, , ceea ce înseamnă că dacă marginile graficului sunt în două culori, va exista întotdeauna un triunghi monocrom. $k$ $K_n$ $K_{s}$ $s$ $R_{k}(e)$ $n\geq R(e)$ $R_{2}(3)=6$ $K_{6}$

Aplicații

Colorarea în linii a graficelor complete poate fi folosită pentru a împărți programul turneelor round robin în mai multe runde, astfel încât fiecare pereche să joace într-una dintre runde. În această aplicație, vârfurile corespund participanților la turneu, iar marginile corespund jocurilor. Culoarea marginilor corespunde cercurilor turneului [45] . O tehnică similară de colorare poate fi folosită pentru alte programe sportive în care nu toată lumea joacă neapărat cu toată lumea. De exemplu, în Liga Națională de Fotbal (Statele Unite, Fotbal American ), perechile de echipe care vor juca într-un anumit an sunt determinate de rezultatele echipelor din anul precedent, iar algoritmul de colorare a marginilor este aplicat graficului format din ansamblul acestor perechi în vederea repartizării jocurilor în weekend, conform cărora se desfășoară jocurile [46] . Pentru această aplicație, teorema lui Vizing înseamnă că indiferent ce set de perechi este ales (atâta timp cât două echipe nu joacă de două ori într-un sezon), este întotdeauna posibil să găsești un program care să surprindă cel mult un weekend în plus (comparativ cu numărul de jocuri pe care le joacă o echipă).

Programul pentru o linie deschisă este o problemă de planificare a unui proces de producție , în care există multe obiecte care trebuie fabricate. Fiecare obiect trebuie să treacă prin anumite proceduri (în orice ordine) și fiecare lucrare trebuie efectuată pe o anumită mașină, în timp ce mașina poate efectua o singură procedură la un moment dat. Dacă toate lucrările au aceeași lungime, atunci problema poate fi pusă ca o linie de colorare a unui graf bipartit, în care vârfurile unei părți reprezintă obiectele de realizat, iar vârfurile celeilalte părți a graficului reprezintă mașini de procesare. . Marginile reprezintă munca de făcut, iar culorile reprezintă intervalele de timp în care trebuie efectuată lucrarea. Deoarece colorarea liniilor unui graf bipartit se poate face în timp polinomial, același lucru este valabil și pentru cazul special specificat de planificare a liniilor deschise [47] .

În 2005 [48] , problema de programare a conexiunii pentru un protocol de comunicație cu acces multiplu cu divizare în timp în rețelele de senzori fără fir a fost studiată ca o variantă de colorare a marginilor. În această problemă, trebuie să alegeți intervalele de timp pentru marginile rețelei fără fir, astfel încât fiecare vârf al rețelei să poată comunica cu vârfurile învecinate fără influență reciprocă. Utilizarea strictă a colorării marginilor (cu două intervale de timp pentru fiecare culoare a marginilor, câte una în fiecare direcție) rezolvă problema, dar numărul de intervale utilizate poate fi mai mult decât necesar. În schimb, ei căutau o colorare a graficului direcționat format prin înlocuirea fiecărei margini nedirecționate cu două arce direcționate, fiecare arc având o culoare diferită față de culorile arcurilor care ies și ale vecinilor săi . Ei au propus un algoritm euristic pentru rezolvarea acestei probleme, bazat pe un algoritm distribuit pentru colorarea marginilor, urmat de un proces de corecție a programului pentru a elimina posibilele interferențe reciproce. $UV$ $v$ $v$ $({\Delta }+1)$

În comunicarea prin fibră optică , problema de atribuire a culorii este problema atribuirii unei frecvențe luminoase unei perechi de vârfuri care necesită comunicare și căi prin rețeaua de fibră pentru fiecare pereche, cu constrângerea ca două căi să nu împartă același segment de fibră. și aceeași frecvență. Căile care trec prin același comutator, dar nu prin același segment de fibră, pot avea aceeași frecvență. Dacă rețeaua este construită ca o stea cu un singur comutator în centru, care este conectat printr-o fibră separată la fiecare nod al rețelei, problema de atribuire a culorilor poate fi modelată exact ca problema colorării marginilor unui grafic sau multigraf. în care nodurile de comunicație formează noduri de graf, perechile de noduri care necesită schimb de informații formează arce, iar frecvența care poate fi utilizată pentru fiecare pereche de noduri corespunde colorării arcelor din problema de colorare. Pentru rețelele de comunicații având o topologie arborescentă mai generală, soluțiile locale la problemele de atribuire a unei culori de cale stelelor formate de fiecare comunicator pot fi reunite pentru a obține o singură soluție globală [49] .

Probleme deschise

Jensen și Toft [50] au enumerat 23 de probleme deschise privind colorarea marginilor. Acestea includ:

Ipoteza lui Goldberg [51] că indicele cromatic și indicele fracționar diferă cu cel mult unul, ceea ce ar permite aproximarea indicelui cromatic cu o eroare de o culoare în timp polinomial.
Unele conjecturi ale lui Jacobsen ( Jakobsen ) și altele despre structura graficelor critice pentru colorarea liniilor grafice din clasa 2, astfel încât orice subgraf fie să aibă un grad maxim mai mic, fie să aibă clasa 1. Jacobsen a presupus inițial că toate graficele critice au un număr impar de vârfuri, dar, în cele din urmă, presupunerea este respinsă. Câteva alte conjecturi mai slabe decât aceasta, precum și presupunerile care limitează numărul de vârfuri ale graficelor critice și ale multigrafurilor critice, rămân deschise.
Problema Vizing de clasificare a gradelor maxime, care este posibilă pentru grafurile plane de clasa 2.
Conjectura asupra graficelor Hilton debordante (AJW Hilton), care afirmă că un grafic cu grad cel puțin fie are clasa 1, fie conține un subgraf de același grad ca și graficul original și pentru un număr impar de vârfuri astfel încât numărul de muchii ale subgraf este mai mare decât . Aproape de aceasta este conjectura lui Herbert Grötsch și Paul Seymour privind graficele plane în loc de graficele de grad înalt. $n/3$ $\Delta$ $k$ $\Delta(k-1)/2$
Conjectura lui Chetwynd și Hilton (posibil înrădăcinată în lucrarea anterioară a lui Dirac că un grafic regulat cu un număr par de vârfuri și grad are cel puțin clasa 1. $n$ $n/2$
Conjectura lui Claudy Berge și Delbert Fulkerson conform căreia multigrafele cu 6 regulate formate prin dublarea fiecărei margini a unui grafic simplu cu 3 puncte regulate pot fi colorate cu șase culori.
Conjectura lui Fiorini și Wilson că orice grafice plane fără triunghiuri , altele decât gheara K 1,3 , nu sunt colorabile în mod unic pentru margini cu 3 culori.

O presupunere mai modernă este, de asemenea, demnă de remarcat: dacă este un multigraf planar obișnuit, atunci este colorabil cu muchia dacă și numai dacă este conectat cu muchia impară . Această presupunere poate fi considerată ca o generalizare a problemei cu patru culori pentru . Maria Chudnovskaya , Katherine Edwards și Paul Seymour au demonstrat că un multigraf planar regulat de 8 are numărul cromatic de muchie 8 [52] . $G$ $d$ $G$ $d$ $G$ $d$ $d=3$

Note

↑ Soifer, 2008 , problema 16.4, p. 133.
↑ Soifer, 2008 .
↑ Soifer, 2008 , problema 16.5, p. 133. Faptul că aveți nevoie de una sau de culori rezultă din teorema Vizing . $n$ $(n-1)$
↑ Biggs, 1972 .
↑ Biggs, 1972 ; Meredith, Lloyd 1973 ; Biggs, 1979 .
↑ 12 Soifer , 2008 , p. 134.
↑ 1 2 König, 1916 .
↑ Erdős, Wilson, 1977 .
↑ Hollier, 1981 .
↑ Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 ; Appel, Haken, 1976 .
↑ Soifer, 2008 , p. 136.
↑ Shannon, 1949 .
↑ 1 2 Cole, Ost, Schirra, 2001 .
↑ Cole, Hopcroft, 1982 .
↑ Alon, 2003 .
↑ Gabov, 1976 .
↑ Cole, Kovalik, 2008 .
↑ Misra, Grise, 1992 .
↑ Gabov și colab., 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, Nisizeki, 1996 .
↑ Nemhauser, Park, 1991 .
↑ Schwenk, 1989 .
↑ Folkman, Fulkerson, 1969 .
↑ Bosack, 1972 .
↑ Richter, 2011 .
↑ Akiyama, Ikzu, Harari 1980 , Habib, Peroshe 1982 , Horak, Nipel 1982 .
↑ Nash Williams, 1964 .
↑ Gabov, Westerman, 1992 .
↑ Galvin, 1995 .
↑ Bosak, Neshetril, 1976 .
↑ Fouquet, Jolivet 1983 ; Mahdian, 2002 ; Friz, Krivelevici, Sudakov, 2005 ; Cranston, 2006 .
↑ Barret et al., 2006 .
↑ Alon, Sudakov, Zaks, 2001 , Muthu, Narayanan, Subramanyan, 2007 .
↑ Epstein, 2010 .
↑ Burke, Werra, Kingston, 2004 .
↑ Skiena, 2008 .
↑ Williamson și colab., 1997 .
↑ Gandham, Davande, Prakash, 2005 .
↑ Elebach, Jensen, 2001 .
↑ Jensen, Toft, 1995 .
↑ Goldberg, 1973 .
↑ Maria Chudnovsky, Katherine Edwards, Paul Seymour. Colorarea marginilor grafice plane cu opt regulate (neopr.) . - 2012. - 13 ianuarie.

Link -uri

Jin Akiyama, Geoffrey Exoo, Frank Harary. Acoperirea și împachetarea în grafice. III. Invarianţi ciclici şi aciclici // Mathematica Slovaca. - 1980. - T. 30 , nr. 4 . - S. 405-417 .
Noga Alon. Un algoritm simplu pentru multigrafe bipartite cu colorarea marginilor // Litere de procesare a informațiilor. - 2003. - T. 85 , nr. 6 . - S. 301-302 . - doi : 10.1016/S0020-0190(02)00446-5 .
Noga Alon, Benny Sudakov, Ayal Zaks. Colorări aciclice de margini ale graficelor // Journal of Graph Theory. - 2001. - T. 37 , nr. 3 . - S. 157-167 . - doi : 10.1002/jgt.1010 .
Lars Dovling Andersen. Despre colorarea marginilor graficelor // Mathematica Scandinavica. - 1977. - T. 40 , nr. 2 . - S. 161-175 . . Așa cum este menționat în [1]
K. Appel, W. Haken. Fiecare hartă plană are patru culori // Buletinul Societății Americane de Matematică. - 1976. - Vol. 82 , iss. 5 . - P. 711-712 . - doi : 10.1090/S0002-9904-1976-14122-5 .
Bahman Bahmani, Aranyak Mehta, Rajeev Motwani. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). - 2010. - S. 31-39 .
Amotz Bar-Noy, Rajeev Motwani, Joseph Naor. Algoritmul greedy este optim pentru colorarea marginilor on-line // Litere de procesare a informațiilor. - 1992. - T. 44 , nr. 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. A patra Conferință Internațională Anuală IEEE privind Atelierele de Calcul Pervasive și Comunicații (Atelierele PerCom 2006). - 2006. - S. 106 . — ISBN 0-7695-2520-2 . - doi : 10.1109/PERCOMW.2006.129 .
Norman Biggs. Probleme de cercetare / Richard K. Guy. — American Mathematical Monthly. - 1972. - T. 79. - S. 1018-1020.
Norman Biggs. A doua conferință internațională de matematică combinatorie // Analele Academiei de Științe din New York. - 1979. - T. 319 . - S. 71-81 . - doi : 10.1111/j.1749-6632.1979.tb32775.x .
Andreas Bjorklund, Thore Husfeldt, Mikko Koivisto. Setați partiționarea prin includere-excludere // SIAM Journal on Computing. - 2009. - T. 39 , nr. 2 . - S. 546-563 . - doi : 10.1137/070683933 .
Juraj Bosak. Indicele cromatic al graficelor finite și infinite // Cehoslovac Mathematical Journal. - 1972. - T. 22 (97) . - S. 272-290 .
Juraj Bosak, Jaroslav Nesetril. Colorări complete și pseudocomplete ale unui grafic // Matematicky Casopis Slovenskej Akademie Vied. - 1976. - T. 26 , nr. 3 . - S. 171-184 .
E. Burke, D. DeWerra, J. Kingston. {{{titlu}}} / JL Gross, J. Yellen. - CRC Press, 2004. - S. 462 . - ISBN 978-1-58488-090-5 .
Guantao Chen, Xingxing Yu, Wenan Zang. Aproximarea indicelui cromatic al multigrafelor // Journal of Combinatorial Optimization. - 2011. - T. 21 , nr. 2 . - S. 219-246 . - doi : 10.1007/s10878-009-9232-y .
Richard Cole, John Hopcroft. Pe margine colorarea graficelor bipartite // SIAM Journal on Computing. - 1982. - T. 11 , nr. 3 . - S. 540-546 . - doi : 10.1137/0211043 .
Richard Cole, Lukasz Kowalik. Noi algoritmi de timp liniar pentru graficele plane de colorare a muchiilor // Algorithmica. - 2008. - T. 50 , nr. 3 . - S. 351-368 . - doi : 10.1007/s00453-007-9044-3 .
Richard Cole, Kirstin Ost, Stefan Schirra. Multigrafe bipartite de colorare a marginilor în timp // Combinatorică . - 2001. - T. 21 , nr. 1 . - P. 5-12 . - doi : 10.1007/s004930170002 . $O(E\log D)$
Daniel W. Cranston. Colorare puternică a marginilor graficelor cu gradul maxim 4 folosind 22 de culori // Matematică discretă . - 2006. - T. 306 , nr. 21 . - S. 2772-2778 . - doi : 10.1016/j.disc.2006.03.053 .
David Eppstein. Proc. 16 Int. Symp. Desen grafic / Ioannis G. Tollis, Marizio Patrignani. - Heraklion, Creta, 2008. - T. 5417. - S. 78-89. — (Note de curs în Informatică).
David Eppstein. Proc. A 22-a Conferință canadiană privind geometria computațională (CCCG 2010). — 2010.
Paul Erdos, Robin J. Wilson. Notă despre indicele cromatic al aproape tuturor graficelor // Journal of Combinatorial Theory . - 1977. - T. 23 , nr. 2-3 . - S. 255-257 . - doi : 10.1016/0095-8956(77)90039-9 .
Thomas Erlebach, Klaus Jansen. Complexitatea colorării căilor și a programării apelurilor // Informatică teoretică. - 2001. - T. 255 , nr. 1-2 . - S. 33-50 . - doi : 10.1016/S0304-3975(99)00152-8 .
S. Fiorini, RJ Wilson. Colorarea marginilor graficelor. - Londra: Pitman, 1977. - V. 16. - (Research Notes in Mathematics). - ISBN 0-273-01129-4 .
Jon Folkman, D. R. Fulkerson. Matematica combinatorică și aplicațiile sale (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967). - Chapel Hill, NC: Univ. North Carolina Press, 1969, p. 561-577.
J.L. Fouquet, J.-L. Jolivet. Colorări puternice de margini ale graficelor și aplicații la mai multe gonuri // Ars Combinatoria. - 1983. - T. 16 , nr. A. _ - S. 141-150 . $k$
Alan M. Frieze, Michael Krivelevich, Benny Sudakov. Indicele cromatic puternic al graficelor aleatorii // SIAM Journal on Discrete Mathematics . - 2005. - T. 19 , nr. 3 . - S. 719-727 (electronic) . - doi : 10.1137/S0895480104445757 .
Harold N. Gabow. Utilizarea partițiilor Euler pentru a delimita multigrafele bipartite color // International Journal of Computer and Information Sciences. - 1976. - V. 5 , nr. 4 . - S. 345-355 . - doi : 10.1007/BF00998632 .
Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algoritmi pentru graficele de colorare a muchiilor. - Universitatea Tohoku, 1985.
Harold N. Gabow, Herbert H. Westermann. Păduri, cadre și jocuri: algoritmi pentru sume și aplicații matroide // Algorithmica. - 1992. - T. 7 , nr. 5-6 . - S. 465-497 . - doi : 10.1007/BF01758774 .
F. Galvin. Lista indexului cromatic al unui multigraf bipartit // Journal of Combinatorial Theory . - 1995. - T. 63 , nr. 1 . - S. 153-158 . - doi : 10.1006/jctb.1995.1011 .
S. Gandham, M. Dawande, R. Prakash. Proc. al 24-lea INFOCOM. - 2005. - T. 4 . - S. 2492-2501 . — ISBN 0-7803-8968-9 . - doi : 10.1109/INFCOM.2005.1498534 .
MK Goldberg. Multigrafe cu un indice cromatic aproape maxim // Diskret. Analiz.. - 1973. - Problema. 23 . - S. 3-7, 72 . . După cum este citat în [1] .
M. Habib, B. Peroche. Câteva probleme despre arboricitatea liniară // Matematică discretă. - 1982. - T. 41 , nr. 2 . - S. 219-220 . - doi : 10.1016/0012-365X(82)90209-6 .
Ian Holyer. Completitudinea NP a colorării marginilor // SIAM Journal on Computing . - 1981. - T. 10 , nr. 4 . - S. 718-720 . - doi : 10.1137/0210055 .
Peter Horak, Ludovit Niepel. O scurtă demonstrație a unei teoreme de arboricitate liniară pentru grafice cubice // Acta Mathematica Universitatis Comeniae. - 1982. - T. 40/41 . - S. 275-277 .
Tommy R. Jensen, Bjarne Toft. Probleme de colorare a graficelor. - New York: Wiley-Interscience, 1995. - ISBN 0-471-02865-7 .
Howard J. Karloff, David Shmoys. Algoritmi paraleli eficienți pentru problemele de colorare a marginilor // Journal of Algorithms. - 1987. - T. 8 , nr. 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 , nr. 4 . - S. 453-465 . - doi : 10.1007/BF01456961 .
Lukasz Kowalik. Colorarea marginilor îmbunătățită cu trei culori // Informatică teoretică. - 2009. - T. 410 , nr. 38-40 . - S. 3733-3742 . - doi : 10.1016/j.tcs.2009.05.005 .
Mohammad Mahdian. Despre complexitatea computațională a colorării marginilor puternice // Matematică aplicată discretă. - 2002. - T. 118 , nr. 3 . - S. 239-248 . - doi : 10.1016/S0166-218X(01)00237-2 .
Guy HJ Meredith, E. Keith Lloyd. Fotbalistii lui Croam // Journal of Combinatorial Theory . - 1973. - T. 15 , nr. 2 . - S. 161-166 . - doi : 10.1016/0095-8956(73)90016-6 .
J. Misra, D. Gries. O dovadă constructivă a teoremei lui Vizing // Litere de procesare a informațiilor . - 1992. - T. 41 , nr. 3 . - S. 131-133 . - doi : 10.1016/0020-0190(92)90041-S .
Rahul Muthu, N. Narayanan, C. R. Subramanian. Limite îmbunătățite ale colorării marginilor aciclice // Matematică discretă . - 2007. - T. 307 , nr. 23 . - S. 3063-3069 . - doi : 10.1016/j.disc.2007.03.006 .
Crispin Nash-Williams. Descompunerea graficelor finite în păduri // Journal of the London Mathematical Society. - 1964. - T. 39 .
George Nemhauser, parcul Sungsoo. O abordare poliedrică a colorării marginilor // Operations Research Letters. - 1991. - T. 10 , nr. 6 . - S. 315-322 . - doi : 10.1016/0167-6377(91)90003-8 .
David A. Richter. Proc. 18th International Symposium on Graph Drawing (GD 2010) / Ulrik Brandes, Sabine Cornelsen. - Springer-Verlag, 2011. - T. 6502. - S. 353-364. — (Note de curs în Informatică). - ISBN 978-3-642-18468-0 . - doi : 10.1007/978-3-642-18469-7_32 .
Daniel P. Sanders, Yue Zhao. Graficele plane de gradul maxim șapte sunt clasa I // Journal of Combinatorial Theory . - 2001. - T. 83 , nr. 2 . - S. 201-212 . - doi : 10.1006/jctb.2001.2047 .
PD Seymour. Despre multicolorări ale graficelor cubice și conjecturi ale lui Fulkerson și Tutte // Proceedings of the London Mathematical Society. - 1979. - T. 38 , nr. 3 . - S. 423-460 . - doi : 10.1112/plms/s3-38.3.423 .
Allen J. Schwenk. Enumerarea ciclurilor hamiltoniene în anumite grafice Petersen generalizate // Journal of Combinatorial Theory . - 1989. - T. 47 , nr. 1 . - S. 53-59 . - doi : 10.1016/0095-8956(89)90064-6 .
Claude Shannon. O teoremă privind colorarea liniilor unei rețele // J. Math. Fizică. - 1949. - T. 28 . - S. 148-151 .
Steven S. Skiena. Manualul de proiectare a algoritmului . - Springer-Verlag, 2008. - S. 548 -550 . - ISBN 978-1-84800-069-8 . - doi : 10.1007/978-1-84800-070-4_16 . . Vezi și [1] în Stony Brook Algorithm Repository.
Alexandru Soifer. Cartea de colorat matematic. - Springer-Verlag, 2008. - ISBN 978-0-387-74640-1 .
PG Tait. Observații asupra colorațiilor hărților // Proc. R. Soc. Edinburgh. - 1880. - T. 10 . - S. 729 .
Trachtman. Problema colorării drumurilor // Israel Journal of Mathematics. - 2009. - T. 172 , nr. 1 . - S. 51-60 . - doi : 10.1007/s11856-009-0062-5 . - arXiv : 0709.0099 .
VG Vizing. Pe o estimare a clasei cromatice a unui p -graph // Diskret. Analiz .. - 1964. - T. 3 . - S. 25-30 .
VG Vizing. Grafice critice cu clasa cromatică dată // Metoda Diskret. Analiz.. - 1965. - V. 5 . - S. 9-17 . . (In rusa.)
DP Williamson, LA Hall, JA Hoogeveen, CAJ Hurkens, JK Lenstra, SV Sevast'janov, DB Shmoys. Programe scurte de magazin // Cercetare operațională. - 1997. - T. 45 , nr. 2 . - S. 288-294 . doi : 10.1287 / opre.45.2.288 . — .
Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki. Arbori parțial de colorare a marginilor // Journal of Algorithms. - 1996. - T. 21 , nr. 3 . - S. 598-617 . - doi : 10.1006/jagm.1996.0061 . $k$

↑ 1 2 Chen, Yu, Zang, 2011 .