Kantfarvning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. september 2022; verifikation kræver 1 redigering .

Kantfarvning er tildelingen af "farver" til kanterne af en graf på en sådan måde, at ikke to tilstødende kanter har samme farve. Kantfarvning er en af de forskellige typer graffarvning. Kantfarveproblemet spørger, om det er muligt at farve kanterne på en given graf med højst forskellige farver for en given værdi eller for det mindst mulige antal farver. Det mindste antal farver, der kræves for at farve kanterne på en given graf, kaldes grafens kromatiske indeks . For eksempel kan kanterne på grafen i illustrationen farves med tre farver, men kan ikke farves med to, så grafen har et kromatisk indeks på 3. $k$ $k$

Ifølge Vizings teorem er antallet af farver, der kræves for en kantfarvning af en simpel graf, enten lig med den maksimale grad af hjørner eller . For nogle grafer, såsom todelte grafer og høje plane grafer , er antallet af farver altid , mens antallet af farver for multigrafer kan være op til . Der er polynomielle tidsalgoritmer, der producerer en optimal farvning af todelte grafer og en farvning af en simpel ikke-todelt graf med antal farver . Men i det generelle tilfælde er problemet med at finde den optimale linjefarvning NP-komplet , og den hurtigste kendte algoritme for den kører i eksponentiel tid. Mange varianter af kantfarvningsproblemet er blevet undersøgt, hvor betingelserne for at tildele en farve til en kant skal opfylde andre betingelser end konjugation. Kantfarvningsproblemerne har anvendelser i planlægningsproblemer og frekvenstildeling i fiberoptiske netværk. $\Delta$ $\Delta +1$ $\Delta$ $3{\Delta }/2$ ${\Delta }+1$

Eksempler

Graf-cyklussen kan farves i 2 farver, hvis længden af cyklussen er lige - brug blot 2 farver efter tur, og passerer sekventielt kanterne af cyklussen. Men i tilfælde af en ulige længde kræves 3 farver [1] .

Kanterne på en komplet graf med hjørner kan farvekodes, hvis de er lige. Dette er et særligt tilfælde af Baranyais sætning . Soifer [2] giver følgende geometriske konstruktion af farven i dette tilfælde: vi placerer punkter i hjørnerne og i midten af en regulær -gon. For hver farveklasse vælger vi en kant, der forbinder midten og en af polygonhjørnerne, og alle kanter vinkelret på den, der forbinder par af polygonhjørner. Men hvis ulige er farver påkrævet - hver farve kan kun bruges til at farve kanter, den -te del af alle kanter [3] . $K_n$ $n$ $n-1$ $n$ $n$ $(n-1)$ $n$ $n$ $(n-1)/2$ $1/n$

Nogle forfattere har studeret kantfarvning af ulige grafer , -regulære grafer, hvor hjørnerne repræsenterer hold af spillere fra et samlet antal spillere, og hvor kanterne repræsenterer mulige par af disse hold (med én offside-spiller til dommer). I det tilfælde hvor vi får den velkendte Petersen graf . Som Biggs forklarer $n$ $(n-1)$ $2n-1$ $n=3$ [4] , problemet (for) er, at spillerne ønsker at finde et skema, således at holdene spiller hver af de seks kampe på forskellige dage i ugen, undtagen søndag for alle spillere. I den matematiske formulering ønsker de at finde en 6-farvet linjefarvning af 6-regulære grafer. Nården er lig med 3, 4 eller 8,kræverfarver, men for 5, 6 og 7 er der kunfarver [5] . $n=6$ $O_{6}$ $n$ $På}$ $n+1$ $n$

Definitioner

Som med vertexfarvning antager kantfarvning af en graf, medmindre andet udtrykkeligt er angivet, altid, at to tilstødende kanter tildeles forskellige farver. To kanter anses for at støde op, hvis de har et fælles toppunkt. En kantfarvning af en graf kan opfattes som ækvivalent til en toppunktfarvning af en linjegraf , en graf, der har et toppunkt for hver kant af grafen og en kant for hvert par af tilstødende kanter . $G$ $L(G)$ $G$ $G$

En ordentlig farvning med forskellige farver kaldes en (rigtig) kantfarvning. Hvis der kan findes en (korrekt) kantfarvning til en graf, siges den at være kantfarverbar . Det mindste antal farver, der er nødvendige for en (korrekt) linjefarvning af en graf , kaldes det kromatiske indeks eller kantkromatiske tal . Det kromatiske indeks skrives nogle gange som . I denne notation angiver indekset, at kanterne er endimensionelle objekter. En graf er kantfarvet, hvis det kromatiske indeks er nøjagtigt . Det kromatiske indeks må ikke forveksles med det kromatiske tal eller det mindste antal farver, der kræves for korrekt at farve toppen af en graf . $k$ $k$ $k$ $k$ $G$ $\chi {\prime }(G)$ $\chi _{1}(G)$ $k$ $k$ $\chi (G)$ $\chi _{0}(G)$ $G$

Medmindre andet er angivet, antages alle grafer at være simple, i modsætning til multigrafer , hvor to eller flere kanter kan forbinde det samme par hjørner, og hvor der kan være sløjfer (en kant, hvis endespidser er de samme). For de fleste linjefarveproblemer opfører simple grafer sig anderledes end multigrafer, og der kræves ekstra forsigtighed, når man udvider linjefarvesætninger fra simple grafer til multigrafer.

Forhold med matchninger

En matchning i en graf er et sæt kanter, hvoraf ikke to støder op til hinanden. En matching kaldes perfekt, hvis dens kanter indeholder alle hjørnerne af grafen og maksimal, hvis den indeholder det maksimalt mulige antal kanter. I en kantfarvning skal kanter af samme farve være ikke-tilstødende, så de danner en match. En korrekt kantfarvning er således det samme som at dekomponere en graf til usammenhængende matchninger. $G$

Hvis størrelsen af den maksimale matchning i en given graf er lille, er der behov for et stort antal matchninger for at dække alle grafens kanter. Mere formelt antager denne forklaring, at hvis en graf har kanter, og hvis et maksimum af kanter kan tilhøre en maksimal matchning, så skal hver kantfarvning af grafen mindst indeholde distinkte farver. [6] For eksempel har den plane graf med 16 toppunkter vist på illustrationen kanter. Der er ingen perfekt matchning i denne graf - hvis det centrale toppunkt hører til matchningen, kan de resterende toppunkter opdeles i tre forbundne grupper med antallet af toppunkter 4, 5, 5. De resulterende subgrafer med et ulige antal toppunkter gør det ikke har et perfekt match. Dog har grafen en maksimal matchning med syv kanter, så . Derfor er antallet af farver, der kræves til en kantfarvning af en graf, mindst 24/7, og da antallet af farver skal være et heltal, får vi mindst 4 farver. $m$ $\beta$ $m/\beta$ $m=24$ $\beta=7$

For almindelige grafer af grad , der ikke matcher perfekt, kan denne nedre grænse bruges til at vise, at der i det mindste er behov for farver. [6] Dette gælder især for almindelige grafer med et ulige antal hjørner. For sådanne grafer skal ved håndtrykslemmaet , , til gengæld være lige . Uligheden forklarer dog ikke fuldt ud det kromatiske indeks for en vilkårlig regulær graf, da der er regulære grafer, som har en perfekt match, men ikke er k -kantfarverbare . For eksempel er Petersen-grafen regulær med og med kanter i perfekt match, men den har ikke en kant 3-farvning. $k$ $k+1$ $k$ $\chi {\prime }\geqslant m\beta$ $m=15$ $\beta=5$

Forholdet til graden

Vizings sætning

Det kromatiske kanttal på en graf er tæt forbundet med den maksimale grad (det maksimale antal kanter, der støder op til et enkelt toppunkt i grafen ). Det er klart , at så hvis forskellige kanter indeholder et toppunkt , så skal alle disse kanter farves med forskellige farver, hvilket kun er muligt, hvis der er mindst farver. Vizings teorem (opkaldt efter Vadim Vizing , som udgav den i 1964) siger, at denne grænse er næsten nøjagtig - for enhver graf er det kromatiske kanttal enten , eller . Hvis , G siges at være af klasse 1, ellers siges det at være af klasse 2. $G$ ${\Delta }(G)$ $G$ $\chi {\prime }(G)\geq {\Delta }(G)$ ${\Delta }$ $v$ $\Delta$ ${\Delta }(G)$ $\Delta (G)+1$ $\chi {\prime }(G)={\Delta }(G)$

Enhver todelt graf har klasse 1 [7] og næsten alle tilfældige grafer har klasse 1 [8] . Men problemet med at kontrollere, om en vilkårlig graf har klasse 1, er et NP-komplet problem [9] .

Vizing [10] beviste, at plane grafer med maksimal grad på mindst otte har klasse 1 og formodede, at det samme gælder for plane grafer af grad 7 eller 6. På den anden side er der plane grafer med maksimal grad mellem to og fem, der har klasse 2. Siden da er formodningen blevet bevist for syv [11] . Plane grafer uden broer Kubiske grafer har klasse 1, og det svarer til formuleringen af firefarveproblemet [12] .

Almindelige grafer

1-faktorisering af en k - regulær graf , det vil sige nedbrydningen af grafens kanter til perfekte matchninger , er det samme som grafens k - kantfarvning. En regulær graf har således en 1-faktorisering, hvis og kun hvis den har klasse 1. Et særligt tilfælde kaldes 3-farve linjefarvningen af kubiske (3-regulære) grafer nogle gange for Tite-farvningen .

Ikke alle almindelige grafer har en 1-faktorisering. Det gør Graf Petersen for eksempel ikke. Snarks defineres som grafer, der ligesom Petersen-grafen er broløse, 3-regulære og af klasse 2.

Ifølge Koenigs sætning [7] har enhver todelt regulær graf en 1-faktorisering. Sætningen blev tidligere formuleret i form af projektive konfigurationer og bevist af Ernst Steinitz .

Multigrafer

For multigrafer , hvor flere kanter kan forbinde de samme to hjørner, kendes lignende, men svagere resultater fra Wizings sætning om kantkromatisk tal , maksimal grad og multiplicitet , maksimalt antal kanter i et bundt af parallelle kanter (det vil sige, at de har samme endetoppe). Som et simpelt eksempel, der viser, at Vizings sætning ikke generaliserer til multigrafer, kan du overveje Shannon multigrafen, en multigraf med tre hjørner og tre bundter af parallelle kanter, der forbinder hvert par af hjørner. I dette eksempel: - er hvert toppunkt kun støder op til to af de tre bundter af parallelle kanter, men det kromatiske tal for kanten er (i kantgrafen er to kanter stødende op, så alle kanter skal farves i forskellige farver). I et papir inspireret af Vizings teorem viste Soifer og Shannon [13] [14] at dette er det værste tilfælde for enhver multigraf . Derudover for enhver multigraf . Denne ulighed reduceres til Vizings teorem for simple grafer (for dem ). $\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$

Algoritmer

Da problemet med at kontrollere, om en graf har klasse 1, er NP-komplet , er der ingen kendt polynomial-tidslinjefarvealgoritme for nogen graf, der giver en optimal farve. Der er dog udviklet en række algoritmer, der svækker et eller flere kriterier: de arbejder på en delmængde af grafer, eller de giver ikke altid det optimale antal farver, eller de virker ikke altid i polynomisk tid.

Optimal farvelægning af nogle specielle klasser af grafer

I tilfælde af todelte grafer eller multigrafer med maksimal grad , er det optimale antal farver nøjagtigt . Det blev vist i 2001 [15] at den optimale linjefarvning af disse grafer kan findes i næsten lineær tid , hvor er antallet af kanter i grafen. Enklere, men noget langsommere algoritmer er tidligere blevet beskrevet af Cole og Hopcroft [16] og Alon [17] . Alons algoritme starter med at gøre grafen regelmæssig uden stor stigning i grad eller stor stigning i størrelse ved at slå par af hjørner, der hører til den samme del af den todelte graf, og derefter tilføje et lille antal hjørner og kanter. Derefter, hvis graden er ulige, finder Alon en perfekt match i lineær tid, tildeler den en farve og fjerner den fra grafen, hvilket resulterer i en graf med lige grad. Til sidst bruger Alon Gabovs observation [18] , at valg af skiftende delmængder af kanter i Euler-cyklussen af en graf opdeler den i to regulære undergrafer, hvilket transformerer kantfarveproblemet til to mindre problemer, så hans algoritme nu løser disse to delproblemer rekursivt . Algoritmens samlede køretid estimeres til . $\Delta$ $\Delta$ $O(m\,\log\Delta )$ $m$ $O(m\,\log m)$

For plane grafer med maksimal grad er det optimale antal farver igen nøjagtigt . Under en strengere antagelse om, at , kan man finde den optimale kantfarvning i lineær tid [19] . ${\Delta }\geq 7$ $\Delta$ ${\Delta }\geq 9$

Algoritmer, der bruger flere farver end nødvendigt for optimal farvelægning

Der er polynomiale-tidsalgoritmer til at farve enhver graf med farver, hvilket svarer til grænsen givet af Vizings sætning [20] [21] . $\Delta +1$

For multigrafer i 1987 [22] er der følgende algoritme (tilskrevet Eli Upfal ): den originale multigraf er lavet Euler ved at tilføje et toppunkt forbundet med kanter til alle hjørner af ulige grader; Euler-stien er fundet, orienteringen for denne vej er valgt; der oprettes en todelt graf, der indeholder to kopier af hvert toppunkt af grafen , en i hver del, og kanter fra et toppunkt i venstre del til et toppunkt i højre del, når en rettet sti har en bue fra til i grafen . Dernæst anvender vi den todelte grafkantfarvealgoritme for grafen . Hver farve i svarer til et sæt kanter i , som danner en subgraf med maksimal grad to, det vil sige en usammenhængende forening af stier og cyklusser, så der for hver farve i kan dannes tre farver i . Algoritmens køretid er begrænset af tidspunktet for farvelægning af en todelt graf ved hjælp af algoritmen fra Cole, Ost og Schirr [15] . Antallet af farver, som denne algoritme bruger, overstiger ikke , hvilket er tæt på, men ikke helt det samme som Shannons bound . Det samme kan gøres med en parallel algoritme direkte. I samme artikel foreslår Karloff og Schmois også en lineær-tidsalgoritme til farvning af multigrafer af højst tredje grad med fire farver (som opfylder både Shannon-bundet og Weezing-bundt). Denne algoritme fungerer efter lignende principper - algoritmen tilføjer også et toppunkt for at gøre grafen Eulerian, finder en Euler-sti og vælger derefter skiftende sæt kanter i stien for at opdele grafen i to delmængder af maksimal grad to. Stierne og lige cyklusser for hver delmængde kan farves i to farver (to farver pr. undergraf). Det næste trin er at farve kanterne af ulige cyklusser, hvor mindst én kant kan farves med en af de to farver, der hører til den modsatte undergraf. Fjernelse af denne kant fra den ulige cyklus efterlader en sti, der kan farves med to farver. $G$ $H$ $G$ $u$ $v$ $u$ $v$ $G$ $H$ $H$ $G$ $H$ $G$ $O(m\,\log\Delta )$ $3\venstre\lceil {\frac {\Delta }2}\right\rceil$ $\venstre\lgulv {\frac {3\Delta }2}\højre\rgulv$

En grådig farvealgoritme , der sekventielt udvælger kanterne på en graf eller multigraf og tildeler den første gyldige farve, kan nogle gange bruge farver, der kan være næsten det dobbelte af det krævede antal farver. Det har dog den fordel, at det kan bruges i online algoritmer , som ikke ved noget om grafens struktur på forhånd. Under disse forhold er dens konkurrencekoefficient lig med to, og denne koefficient er optimal - ingen anden algoritme kan give bedre indikatorer [23] . Men hvis kanterne ankommer i tilfældig rækkefølge, og den originale graf har mindst en logaritmisk grad, kan en mindre konkurrencekoefficient opnås [24] . $2{\Delta}-1$

Nogle forfattere antog, at det kromatiske brøkindeks for enhver multigraf (et tal, der kan beregnes i polynomisk tid ved hjælp af lineær programmering ) ikke adskiller sig fra det kromatiske indeks med mere end én [25] . Hvis formodningen er korrekt, vil det være muligt at finde et tal, der ikke afviger mere end én fra det kromatiske indeks ved multigrafer, hvilket svarer til Vizings sætning for simple grafer. Selvom formodningen i det generelle tilfælde ikke er blevet bevist, er det kendt, at det er sandt, hvis det kromatiske indeks ikke er mindre end , ligesom i tilfældet med multigrafer med tilstrækkelig stor multiplicitet [26] . ${\Delta }+{\sqrt {{\Delta }/2))$

Nøjagtige algoritmer

Det er nemt at kontrollere, om en graf kan være kantfarvet med en eller to farver, så det første ikke-trivielle tilfælde af farvning er at kontrollere, om en graf kan kantfarves med tre farver. I 2009 [27] blev det vist, at det er muligt at kontrollere, om der er en kantfarvning af en graf med tre farver i tid ved kun at bruge et polynomium. Selvom disse tidsgrænser er eksponentielle, er det væsentligt hurtigere end brute-force søgealgoritmen ved at se på alle mulige kantfarver. Enhver dobbeltforbundet 3-regulær vertex-graf har 3-kantsfarver. Og dem alle kan listes i tid (lidt langsommere end tidspunktet for søgning efter én farve). Som Kuperberg bemærkede , har grafen for et prisme over en -gon mange farver, hvilket viser, at denne grænse er nøjagtig [28] . $O(1,344^{n})$ $n$ $O(2^{{n/2}})$ $O(2^{{n/2}})$ $n/2$

Ved at anvende nøjagtige algoritmer til farvning af hjørnerne af en linjegraf , kan man optimalt kantfarve enhver graf med kanter, uanset antallet af nødvendige farver, i tid ved hjælp af eksponentielt rum eller i tid og polynomium [29] . $m$ $2^{m}m^{{O(1)}}$ $O(2,2461^{m})$

Da kantfarvningsproblemet er NP-komplet selv for tre farver, er det usandsynligt, at det egner sig til en fast parametrisering med antallet af farver. Opgaven egner sig dog til parametrering med andre parametre. Især Zhou, Nakano og Nishiseki [30] viste, at for træbreddegrafer kan den optimale linjefarvning findes i tiden , som vokser eksponentielt fra , men kun lineært fra antallet af grafens toppunkter . $w$ $O(nw(6w)^{{w(w+1)/2}})$ $w$ $n$

I 1991 [31] blev kantfarvningsproblemet formuleret som et heltalsprogrammeringsproblem, og der blev udført eksperimenter med heltalsprogrammeringspakker til kantfarvning af grafer, men der blev ikke givet nogen analyse af kompleksiteten af sådanne algoritmer.

Yderligere egenskaber

En graf er entydigt kantfarverbar, hvis og kun hvis der kun er én måde at opdele kanterne i farveklasser, uden at tælle mulige permutationer af farver. For unikt kantfarverbare grafer er kun stier, cyklusser og stjerner , men for andre grafer kan grafer være unikt kantfarverbare. Enhver unikt 3-kant-farverbar graf har præcis tre Hamilton-cyklusser (dannet ved at fjerne en af de tre farver), men der er 3-regulære grafer, der har tre Hamilton-cyklusser, men som ikke har en unik 3-kant-farvning, som f.eks. generaliserede Petersen-grafer for . Der kendes kun én ikke-plan, unikt 3-kant-farverbar graf, dette er den generaliserede Petersen-graf , og der er en formodning om, at der ikke er andre [32] . $k$ $k$ $k!$ $k\neq 3$ $k$ $k = 3$ $k$ $G(6n+3,2)$ $n\geq 2$ $G(9,2)$

Folkman og Fulkerson [33] undersøgte ikke-stigningssekvenser af tal, for hvilke der er en kantfarvning af en given graf med kanter af den første farve, kanter af den anden farve, og så videre. De bemærkede, at hvis en sekvens passer i den beskrevne betydning, og hvis den er leksikografisk større end en sekvens med samme sum, så passer den. Hvis det er leksikografisk, kan det konverteres til trin for trin, ved at reducere et af tallene med et ved hvert trin og øge det næste tal ( ) med et. Med hensyn til kantfarvning starter vi med farvning , udveksler derefter farve sekventielt og i Kempe-kæden , den længste vej af kanter, der veksler mellem to farver. Især har enhver graf en retfærdig linjefarvning, en kantfarvning med et optimalt antal farver, hvor to klasser af farver adskiller sig i størrelse med højst én. $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$ $jeg$ $j$

De Bruijn-Erdős sætning kan bruges til at udvide mange egenskaber ved linjefarvning fra endelige til uendelige grafer . For eksempel kan Shannons og Vizings sætninger om forholdet mellem graden af en graf og dens kromatiske indeks begge let generaliseres til uendelige grafer [34] .

I 2011 [35] blev problemet med at finde et billede af en given kubisk graf med de egenskaber, at alle kanter i billedet har en af tre forskellige hældningsvinkler, og ikke to kanter ligger på samme linje, overvejet. Hvis der findes en sådan repræsentation af grafen i figuren, er det klart, at hældningsvinklen af kanterne kan betragtes som farven på kanterne i en trefarvet farvning af grafen. For eksempel repræsenterer mønsteret af kanter og lange diagonaler af en regulær sekskant en kant 3-farvning af en graf på denne måde. Det er vist, at en 3-regulær todelt graf med en given Tite-farve har en grafisk repræsentation af denne form, hvis og kun hvis den er k-kant-forbundet . For ikke-todelte grafer er betingelsen lidt mere kompliceret - en given farvning kan repræsenteres af et sådant mønster, hvis grafens dobbelte todelte omslag er 3-kantet forbundet, og hvis fjernelse af to ens farvede kanter fører til en ikke-todelt dæksel. underafsnit. Alle disse betingelser er lette at kontrollere i polynomisk tid, men problemet med at kontrollere, om en 4-kantsfarvet 4-regulær graf har et mønster med fire hældninger svarende til farver, er komplet for teorien om eksistensen af reelle tal . samme kompleksitetsklasse som NP-fuldstændighed . $K_{{3,3}}$

Det kromatiske indeks har en sammenhæng med den maksimale grad og det maksimale antal matchninger af en graf, og det kromatiske indeks er også tæt forbundet med grafens trælighed , det mindste antal lineære skove (usammenhængende forening af stier), hvori grafens kanter kan opdeles. Matching er en speciel form for lineær skov, men på den anden side kan enhver lineær skov være 2-kantet, så for enhver . Akiyamas formodning siger, at , hvilket ville indebære en stærkere ulighed . For grafer med maksimal grad er tre altid nøjagtigt lig med to, så begrænsningen svarer til den grænse, der følger af Vizings sætning [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)$

Andre typer kantfarvning

Grafens Thue-tal er antallet af farver, der skal til for en kantfarvning, der opfylder et stærkere krav end enhver lige længde sti, nemlig at den første og anden halvdel af stien skal danne forskellige farvesekvenser.

Træetheden af en graf er det mindste antal farver, der er nødvendige for at farvelægge på en sådan måde, at kanterne af enhver farve ikke indeholder cyklusser (og ikke, som i standardfarveproblemet, kanter af samme farve ikke støder op til hinanden). Dette er således det mindste antal elementer i skoven , som kanterne af grafen kan nedbrydes i [37] . I modsætning til det kromatiske tal kan skovbredden beregnes i polynomisk tid [38] .

Problemet med foreskrevet kantfarvning er et problem, hvor det for en given graf, for hver bue, som en liste over farver er givet, er nødvendigt at finde en passende kantfarvning, hvor hver farve er taget fra en givet liste. Det foreskrevne kromatiske indeks for en graf er det mindste tal, som uanset valget af kantfarvelister, hvis hver kant er givet mindstfarver, garanteres at eksistere en farve. Det foreskrevne kromatiske indeks er altid ikke mindre end det kromatiske tal. Dinitz's formodning om udfyldning af delvise latinske kvadrater kan omformuleres som udsagnet om, at det foreskrevne kantkromatiske tal på en komplet todelt graf er lig med dets kantkromatiske tal. I 1995 [39] blev formodningen løst, og en stærkere påstand blev bevist, at for enhver todelt graf er det kromatiske indeks og det foreskrevne kromatiske indeks ens. En endnu mere generel formodning anføres om ligheden mellem det kromatiske tal og det foreskrevne kromatiske tal for vilkårlige multigrafer uden sløjfer. Denne hypotese forbliver åben. $G$ $k$ $k$ $K_{{n,n}}$ $n$

Mange variationer af toppunktsfarvningsproblemet, der er blevet undersøgt, er blevet udvidet til kantfarvning. F.eks. er fuldkantfarvningsproblemet en variant af fuldfarvning , den korrekte farvning af hjørner, hvor ethvert farvepar skal være til stede mindst én gang i sættet af konjugerede hjørner, og problemet er at maksimere det samlede antal farver [40] . Streng kantfarvning er en variant af streng kantfarvning , hvor to vilkårlige kanter med tilstødende endespidser skal have forskellige farver [41] . Strenge kantfarvning bruges i kanallayoutet for trådløse netværk [42] . En acyklisk linjefarvning er en variant af en acyklisk farve , hvor to vilkårlige farver danner en acyklisk undergraf (det vil sige en skov) [43] .

I 2008 [28] blev en 3-linjers farvning af kubiske grafer undersøgt med den yderligere egenskab, at ikke to tofarvecyklusser har mere end én fælles kant; især blev det vist, at eksistensen af en sådan farvning svarer til eksistensen af en graf, der tegner på et tredimensionelt heltalsgitter med kanter på linjer , parallelt med koordinatakserne, og hver sådan linje indeholder højst to hjørner. Men som i tilfældet med standard 3-kantsfarvningsproblemet, er det et NP-komplet problem at finde en farve af denne type.

Totalfarvning er en farvetype, der kombinerer top- og kantfarvning, hvor både spidser og kanter farves. Ethvert toppunkt og den kant det er enden af, eller to tilstødende kanter skal have forskellige farver, samt to tilstødende toppunkter. Der er en formodning (ved at kombinere Vizings sætning og Brooks' sætning ), at enhver graf har en samlet farve, hvor antallet af farver ikke overstiger den maksimale effekt plus to. Hypotesen er ikke blevet bevist.

Hvis en 3-regulær graf på en overflade er 3-kant-farverbar, danner dens dobbeltgraf en triangulering af overfladen, som også er kantfarverbar (selv om linjefarvning generelt ikke er korrekt) i den forstand, at hver trekant er farvet med tre farver, en kant pr. farve. Andre farvelægninger og orienteringer af trekanter kan sammen med andre lokale begrænsninger for, hvordan farver fordeles over hjørnerne eller flader af en triangulering, bruges til at kode visse typer geometriske objekter. For eksempel kan rektangulære underinddelinger (dele af en rektangulær opdeling af et rektangel i mindre rektangler, hvor tre rektangler mødes i hvert punkt) beskrives kombinatorisk ved "regelmæssig markering", en tofarvet farvning af kanterne på en trianguleringsgraf dual til en rektangulær underopdeling, med den begrænsning, at kanterne støder op til hvert vertex , danner fire grupper af kanter, der går (med uret) i en række. Inden for hver gruppe er kanterne malet i samme farve og har samme retning. Denne markering er dobbelt til farven af selve raffinementet, hvor de lodrette kanter har en farve og de vandrette kanter en anden. Lignende lokale begrænsninger på rækkefølgen af farvede kanter for et toppunkt kan bruges til at kode indlejringen af plane grafer i et gitter dannet af lige linjer og 3D polyedre med flader parallelle med koordinatplanerne. For hver af disse tre typer regulære markeringer danner sættet af regulære markeringer et distributivt gitter , som kan bruges til hurtigt at opregne alle geometriske strukturer baseret på den samme graf, eller finde en struktur der opfylder yderligere begrænsninger [44] .

En deterministisk endelig automat kan repræsenteres som en rettet graf , hvor hvert toppunkt har den samme udgrad af toppunkter, og hvor kanterne er farvet på en sådan måde, at to kanter med samme startpunkt har forskellige farver. Vejfarveproblemet er et linjefarvningsproblem for en rettet graf med samme udgrad, således at den resulterende automat har et synkroniseringsord . Trachtman ( Trachtman 2009 ) løste vejfarveproblemet ved at bevise, at en sådan farvning kan findes, hvis den givne graf er stærkt forbundet og aperiodisk . $d$

Ramseys sætning omhandler problemet med at farvelægge kanterne på en stor komplet graf for at undgå at skabe monokromatiske komplette undergrafer af en given størrelse . Ifølge sætningen eksisterer der et tal , så det er umuligt for den angivne farve. For eksempel, , hvilket betyder, at hvis grafens kanter er 2-farvede, vil der altid være en monokrom trekant. $k$ $K_n$ $K_{s}$ $s$ $R_{k}(r)$ $n\geq R(s)$ $R_{2}(3)=6$ $K_{6}$

Ansøgninger

Linjefarvning af komplette grafer kan bruges til at opdele tidsplanen for round robin-turneringer i flere runder, så hvert par spiller i en af runderne. I denne applikation svarer hjørnerne til deltagerne i turneringen, og kanterne svarer til spillene. Farven på kanterne svarer til turneringens cirkler [45] . En lignende farveteknik kan bruges til andre sportsskemaer, hvor ikke alle nødvendigvis spiller alle. For eksempel, i National Football League (USA, American Football ) bestemmes de holdpar, der skal spille i et givet år, af holdenes resultater i det foregående år, og kantfarvealgoritmen anvendes på grafen dannet af sættet af disse par for at fordele spillene over weekenden, ifølge hvilke spillene finder sted [46] . For denne applikation betyder Vizings teorem, at uanset hvilket sæt af pardannelser, der vælges (så længe der ikke er to hold, der spiller to gange i en sæson), er det altid muligt at finde et skema, der maksimalt fanger en ekstra weekend (sammenlignet med antallet af kampe, et hold spiller).

Tidsplanen for en åben linje er et problem med at planlægge en produktionsproces , hvor der er mange objekter, der skal fremstilles. Hvert objekt skal gennemgå nogle procedurer (i vilkårlig rækkefølge), og hvert job skal udføres på en bestemt maskine, mens maskinen kun kan udføre én procedure ad gangen. Hvis alle job har samme længde, kan problemet opstå som en linjefarvning af en todelt graf, hvor hjørnerne af den ene del repræsenterer de objekter, der skal laves, og hjørnerne i den anden del af grafen repræsenterer forarbejdningsmaskiner . Kanterne repræsenterer det arbejde, der skal udføres, og farverne repræsenterer de tidsintervaller, hvor arbejdet skal udføres. Da linjefarvningen af en todelt graf kan udføres i polynomisk tid, gælder det samme for det specificerede specielle tilfælde af åben linjeplanlægning [47] .

I 2005 [48] blev forbindelsesplanlægningsproblemet for en kommunikationsprotokol med tidsdelt multiadgang i trådløse sensornetværk undersøgt som en variant af kantfarvning. I denne opgave skal du vælge tidsintervallerne for det trådløse netværks kanter, så hvert hjørne af netværket kan kommunikere med nabospidser uden gensidig indflydelse. Brug af streng kantfarvning (med to tidsintervaller for hver kantfarve, en i hver retning) løser problemet, men antallet af anvendte spænd kan være mere end nødvendigt. I stedet ledte de efter en farvning af den rettede graf dannet ved at erstatte hver urettede kant med to rettede buer, hvor hver bue havde en anden farve end farverne på de buer, der udgår fra og dens naboer . De foreslog en heuristisk algoritme til at løse dette problem, baseret på en distribueret algoritme for kantfarvning efterfulgt af en tidsplankorrektionsproces for at fjerne mulig gensidig interferens. $UV$ $v$ $v$ $({\Delta }+1)$

I fiberoptisk kommunikation er farvetildelingsproblemet problemet med at tildele en lysfrekvens til et par hjørner, der kræver kommunikation og stier gennem fibernetværket for hvert par, med den begrænsning, at ikke to stier deler det samme fibersegment og samme frekvens. Stier, der går gennem den samme switch, men ikke gennem det samme fibersegment, må have samme frekvens. Hvis netværket er bygget som en stjerne med en enkelt switch i midten, som er forbundet med en separat fiber til hver knude på netværket, kan farvetildelingsproblemet modelleres nøjagtigt som problemet med at farve kanterne på en graf eller multigraf hvor kommunikationsknudepunkter danner grafnoder, par af noder, der har brug for udveksling af information, danner buer, og frekvensen, der kan bruges for hvert par knudepunkter, svarer til farven af buerne i farveopgaven. For kommunikationsnetværk med en mere generel trætopologi kan lokale løsninger på problemerne med at tildele en stifarve til stjernerne dannet af hver kommunikator samles for at opnå en enkelt global løsning [49] .

Åbne numre

Jensen og Toft [50] anførte 23 åbne problemer vedrørende kantfarvning. Disse omfatter:

Goldbergs hypotese [51] om, at det kromatiske indeks og brøkindekset ikke afviger mere end én, hvilket ville tillade det kromatiske indeks at blive tilnærmet med en fejl på én farve i polynomisk tid.
Nogle formodninger af Jacobsen ( Jakobsen ) og andre om strukturen af kritiske grafer til linjefarvning af grafer i klasse 2, således at enhver undergraf enten har en lavere maksimal grad eller har klasse 1. Jacobsen antog oprindeligt, at alle kritiske grafer har et ulige antal af hjørner, men i sidste ende bliver antagelsen tilbagevist. Adskillige andre formodninger, der er svagere end denne, såvel som formodninger, der begrænser antallet af hjørner af kritiske grafer og kritiske multigrafer, forbliver åbne.
Vizing-problemet med klassificering af maksimale grader, hvilket er muligt for klasse 2 plane grafer.
Formodning om overfyldte Hilton-grafer (AJW Hilton), der angiver, at en graf med grad mindst enten har klasse 1 eller indeholder en undergraf af samme grad som den originale graf, og for et ulige antal hjørner , således at antallet af kanter af subgraf er større end . Tæt på dette er formodningen af Herbert Grötsch og Paul Seymour om plane grafer i stedet for grafer af høj grad. $n/3$ $\Delta$ $k$ $\Delta(k-1)/2$
Chetwynd og Hiltons formodning ( muligvis forankret i Diracs tidligere arbejde , at en regulær graf med et lige antal hjørner og grad har mindst klasse 1. $n$ $n/2$
Formodningen fra Claudy Berge og Delbert Fulkerson om, at 6-regulære multigrafer dannet ved at fordoble hver kant af en 3-regulær broløs simpel graf, kan farves med seks farver.
Fiorini og Wilsons formodning om, at nogen plane grafer uden trekanter , bortset fra kloen K 1,3 , ikke er entydigt kantfarverbare med 3 farver.

En mere moderne formodning er også bemærkelsesværdig: hvis er en -regulær plan multigraf, så er den kant- farverbar, hvis og kun hvis den er ulige kant- forbundet. Denne formodning kan betragtes som en generalisering af firefarveproblemet for . Maria Chudnovskaya , Katherine Edwards og Paul Seymour beviste, at en 8-regulær plan multigraf har kantkromatisk nummer 8 [52] . $G$ $d$ $G$ $d$ $G$ $d$ $d=3$

Noter

↑ Soifer, 2008 , opgave 16.4, s. 133.
↑ Soifer, 2008 .
↑ Soifer, 2008 , opgave 16.5, s. 133. Det faktum, at du har brug for enten eller farver, følger af Vizing-sætningen . $n$ $(n-1)$
↑ Biggs, 1972 .
↑ Biggs, 1972 ; Meredith, Lloyd 1973 ; Biggs, 1979 .
↑ 12 Soifer , 2008 , s. 134.
↑ 1 2 König, 1916 .
↑ Erdős, Wilson, 1977 .
↑ Hollier, 1981 .
↑ Vizing, 1965 .
↑ Sanders, Zhao, 2001 .
↑ Tait, 1880 ; Appel, Haken, 1976 .
↑ Soifer, 2008 , s. 136.
↑ Shannon, 1949 .
↑ 1 2 Cole, Ost, Schirra, 2001 .
↑ Cole, Hopcroft, 1982 .
↑ Alon, 2003 .
↑ Gabov, 1976 .
↑ Cole, Kovalik, 2008 .
↑ Misra, Grise, 1992 .
↑ Gabov et al., 1985 .
↑ Karlof, Schmois, 1987 .
↑ Bar-Noy, Motwani, Naor, 1992 .
↑ Bahmani, Mehta, Motwani, 2010 .
↑ Goldberg 1973 , Andersen 1977 , Seymour 1979 .
↑ Chen, Yu, Zang, 2011 .
↑ Kovalik, 2009 .
↑ 1 2 Epstein, 2008 .
↑ Björklund, Husfeld, Koivisto, 2009 .
↑ Zhou, Nakano, Nishizeki, 1996 .
↑ Nemhauser, 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, Krivelevich, 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 et al., 1997 .
↑ Gandham, Davande, Prakash, 2005 .
↑ Elebach, Jensen, 2001 .
↑ Jensen, Toft, 1995 .
↑ Goldberg, 1973 .
↑ Maria Chudnovsky, Katherine Edwards, Paul Seymour. Kantfarve otte-regulære plane grafer (neopr.) . - 2012. - 13. januar.