Kantfärgning - Edge coloring

En 3-kant-färgning av Desargues-grafen

I grafteorin är en kantfärgning av en graf en tilldelning av "färger" till kanterna på grafen så att inga två infallande kanter har samma färg. Till exempel visar figuren till höger en kantfärgning av ett diagram med färgerna rött, blått och grönt. Kantfärgningar är en av flera olika typer av graffärgning . Den kant-färgning problem frågar om det är möjligt att färga kanterna av en given graf med användning på de flesta $k$ olika färger, för ett givet värde på $k$ , eller med minst antal möjliga färger. Det minsta antal färger som krävs för kanterna på en given graf kallas grafens kromatiska index . Till exempel kan kanterna på grafen i illustrationen färgas med tre färger men kan inte färgas med två färger, så grafen som visas har kromatiskt index tre.

Enligt Vizinges sats är antalet färger som behövs för att kantfärga ett enkelt diagram antingen dess maximala grad $Δ$ eller $Δ+1$ . För vissa grafer, som bipartitgrafer och plana grafer i hög grad , är antalet färger alltid $Δ$ , och för multigrafer kan antalet färger vara så stort som $3Δ/2$ . Det finns polynomiska tidsalgoritmer som konstruerar optimala färgningar av bipartitgrafer och färgningar av icke-bipartit enkla grafer som använder högst $Δ+1$ färger; det allmänna problemet med att hitta en optimal kantfärgning är dock NP-hård och de snabbaste kända algoritmerna för det tar exponentiell tid. Många variationer av kantfärgningsproblemet, där tilldelningar av färger till kanter måste uppfylla andra villkor än icke-angränsande, har studerats. Kantfärgningar har applikationer i schemaläggningsproblem och i frekvenstilldelning för fiberoptiska nät.

Exempel

En cykeldiagram kan ha sina kanter färgade med två färger om cykelns längd är jämn: varva bara de två färgerna runt cykeln. Men om längden är udda behövs tre färger.

Geometrisk konstruktion av en 7-kant-färgning av hela grafen

K 8

. Var och en av de sju färgklasserna har en kant från mitten till en polygonpunkt och tre kanter vinkelrätt mot den.

En komplett graf $K n$ med $n$ hörn är kantfärgbar med $n- 1$ färger när $n$ är ett jämnt tal; detta är ett specialfall av Baranyai sats . Soifer (2008) tillhandahåller följande geometriska konstruktion av en färgning i det här fallet: placera $n$ punkter vid hörnen och mitten av en vanlig $(n$ -1 $)$ -sidig polygon. För varje färgklass, inkludera en kant från mitten till en av polygonhörnen och alla vinkelräta kanter som förbinder par med polygonhörn. Men när $n$ är udda behövs $n$ färger: varje färg kan endast användas för $(n - 1)/ 2$ kanter, en $1/ n$ bråkdel av totalen.

Flera författare har studerat kantfärgningar av de udda grafer , $n$ -regular grafer i vilka spetsarna representerar grupper av $n - 1$ spelare utvalda från en pool av $2 n - 1$ spelare, och i vilket kanterna representerar möjliga parningar av dessa lag (med en spelare kvar som "udda man ute" för att döma spelet). Fallet som $n = 3$ ger den välkända Petersen-grafen . När Biggs (1972) förklarar problemet (för $n = 6$ ) vill spelarna hitta ett schema för dessa par så att varje lag spelar var och en av sina sex matcher på olika dagar i veckan, med söndagar lediga för alla lag; det vill säga att formalisera problemet matematiskt, de vill hitta en 6-kant-färgning av den 6-regelbundna udda grafen $O 6$ . När $n$ är 3, 4 eller 8 kräver en kantfärgning av $O n$ $n + 1$ färger, men när det är 5, 6 eller 7 behövs bara $n$ färger.

Definitioner

Precis som med dess toppunkt motsvarar en kantfärgning av en graf, när den nämns utan någon kvalifikation, alltid en korrekt färgning av kanterna, vilket betyder att inga två intilliggande kanter tilldelas samma färg. Här anses två distinkta kanter vara intilliggande när de delar en gemensam toppunkt. En kant färgning av en graf $G$ kan också tänkas som motsvarar en toppunkt färgning av linjediagrammet $L (G)$ , grafen som har en vertex för varje kant hos $G$ och en kant för varje par av intilliggande kanter i $G$ .

En riktig kantfärgning med $k$ olika färger kallas en (korrekt) $k$ -kantfärgning. En graf som kan tilldelas en $k$ -kantfärgning sägs vara $k$ -kantfärgbar. Det minsta antalet färger som behövs för en (korrekt) kantfärgning av en graf $G$ är det kromatiska indexet eller kantkromatiska talet $χ ' (G)$ . Det kromatiska indexet skrivs också ibland med notationen $χ 1 (G)$ ; i denna notering indikerar abonnemanget att kanterna är endimensionella objekt. En graf är $k$ -kant -kromatisk om dess kromatiska index är exakt $k$ . Den kromatiska indexet bör inte förväxlas med den kromatiska nummer $χ (G)$ eller $χ 0 (G)$ , det minsta antalet färger som behövs i en ordentlig vertex färgning av $G$ .

Om inte annat anges antas alla grafer vara enkla, till skillnad från multigrafer där två eller flera kanter kan ansluta samma par slutpunkter och där det kan finnas självslingor. För många problem med kantfärgning uppträder enkla grafer annorlunda än multigraf, och ytterligare försiktighet krävs för att utvidga satser om kantfärgningar av enkla grafer till multigrafikfodralet.

Relation till matchning

Denna 3-regelbundna plana graf har 16 hörn och 24 kanter, men endast 7 kanter i maximal matchning. Därför kräver det fyra färger i valfri kantfärgning.

En matchning i en graf $G$ är en uppsättning kanter, av vilka inga två är angränsande; en perfekt matchning är en matchning som inkluderar kanter som berör alla hörn i grafen, och en maximal matchning är en matchning som innehåller så många kanter som möjligt. I en kantfärgning måste uppsättningen kanter med valfri färg inte vara i anslutning till varandra, så att de bildar en matchning. Det vill säga, en riktig kantfärgning är samma sak som en uppdelning av grafen i ojämna matchningar.

Om storleken på en maximal matchning i en given graf är liten, kommer många matchningar att behövas för att täcka alla kanterna på grafen. Uttryckt mer formellt innebär detta resonemang att om en graf har $m$ -kanter totalt, och om högst $β$ -kanter kan tillhöra en maximal matchning, måste varje kantfärgning av grafen använda minst $m /β$ olika färger. Till exempel har den 16-vertexa plana grafen som visas i illustrationen $m = 24$ kanter. I den här grafen kan det inte finnas någon perfekt matchning; för om mittpunkten matchas kan de återstående oöverträffade hörnen grupperas i tre olika anslutna komponenter med fyra, fem och fem hörn, och komponenterna med ett udda antal hörn kan inte matchas perfekt. Grafen har dock maximala matchningar med sju kanter, så $β = 7$ . Därför är antalet färger som behövs för att kantfärga grafen minst 24/7, och eftersom antalet färger måste vara ett heltal är det minst fyra.

För en vanlig graf över grad $k$ som inte har en perfekt matchning kan denna nedre gräns användas för att visa att minst $k + 1$ färger behövs. I synnerhet gäller detta för en vanlig graf med ett udda antal hörn (till exempel de udda kompletta graferna); för sådana grafer, genom handskakande lemma , måste $k i$ sig vara jämnt. Ojämlikheten $χ ' \geq m /β$ förklarar dock inte helt det kromatiska indexet för varje vanlig graf, eftersom det finns vanliga grafer som har perfekta matchningar men som inte är k -kantfärgbara. Till exempel är Petersen-grafen regelbunden, med $m = 15$ och med $β = 5$ kanter i sina perfekta matchningar, men den har inte en trekantig färgning.

Förhållande till examen

Vizing's sats

Kanten kromatiska antalet en graf $G$ är mycket nära besläktad med den maximala graden $Δ (G)$ , det största antalet kanter händelsen till någon enskild vertex av $G$ . Uppenbarligen, $χ ' (G) \geq Δ (G)$ , för om $Δ$ olika kanter möts vid samma hörn $v$ , måste alla dessa kanter tilldelas olika färger från varandra, och det kan bara vara möjligt om det finns åtminstone $Δ$ färger tillgängliga för tilldelning. Vizing's sats (uppkallad efter Vadim G. Vizing som publicerade den 1964) säger att denna gräns är nästan tätt: för vilken graf som helst är kantkromatiskt tal antingen $Δ (G)$ eller $Δ (G) + 1$ . När $χ '(G) = Δ (G)$ , G sägs vara av klass 1; annars sägs det vara klass 2.

Varje bipartitdiagram är av klass 1, och nästan alla slumpmässiga grafer är av klass 1. Det är dock NP-komplett att avgöra om ett godtyckligt diagram är av klass 1.

Vizing (1965) visade att plana grafer med högsta grad åtminstone åtta är av klass ett och gissade att samma sak gäller för plana grafer med högsta grad sju eller sex. Å andra sidan finns det plana grafer med maximal grad som sträcker sig från två till fem som är av klass två. Gissningen har sedan bevisats för grafer med högsta grad sju. Bridgeless plana kubiska grafer är alla av klass 1; detta är en ekvivalent form av fyrfärgsatsen .

Vanliga grafer

En 1-faktorisering av en k - regelbunden graf , en partition av kanterna hos grafen i perfekta matchningar , är samma sak som en k -edge-färgning av grafen. Det vill säga, en vanlig graf har en 1-faktorisering om och bara om den är av klass 1. Som ett speciellt fall av detta kallas ibland en 3-kant-färgning av en kubisk (3-vanlig) graf en Tait-färgning .

Inte varje vanlig graf har en 1-faktorisering; till exempel gör inte Petersen -grafen . Mer generellt definieras snarkarna som de grafer som, liksom Petersen-grafen, är brolösa, 3-regelbundna och klass 2.

Enligt satsen i Kőnig (1916) har varje tvåparts regelbunden graf en 1-faktorisering. Satsen angavs tidigare när det gäller projektiva konfigurationer och bevisades av Ernst Steinitz .

Multigrafer

En Shannon -multigraf med grad sex och kantmultiplicitet tre, som kräver nio färger i valfri kantfärgning

För multigrafer , där flera parallella kanter kan ansluta samma två hörn, är resultat som liknar men svagare än Vizinges sats kända för kantkromatiskt tal $χ ' (G)$ , maximal grad $Δ (G)$ och multiplicitet $μ (G)$ , det maximala antalet kanter i alla buntar med parallella kanter. Som ett enkelt exempel som visar att Vizinges sats inte generaliseras till multigraf, överväga en Shannon -multigraf , en multigraf med tre hörn och tre buntar med $μ (G)$ parallella kanter som förbinder vart och ett av de tre hörnparen. I det här exemplet är $Δ (G) = 2μ (G)$ (varje toppunkt infaller endast två av de tre buntarna med $μ (G)$ parallella kanter) men det kromatiska $kanttalet$ är $3μ ($ $G$ $)$ (det finns $3μ (G)$ kanter totalt och varannan kant ligger intill varandra, så alla kanter måste tilldelas varandra olika färger). I ett resultat som inspirerade Vizing, Shannon (1949) visade att detta är det värsta fallet: $χ '(G) \leq (3/2) Δ (G)$ för varje Multigraph $G$ . För varje multigraf $G$ , $χ ' (G) \leq Δ (G) + μ (G)$ , en ojämlikhet som reduceras till Vizinges sats när det gäller enkla grafer (för vilka $μ (G) = 1$ ).

Algoritmer

Eftersom problemet med att testa om en graf är klass 1 är NP-komplett , finns det ingen känd polynomisk tidsalgoritm för kantfärgning av varje graf med ett optimalt antal färger. Ändå har ett antal algoritmer utvecklats som släpper upp ett eller flera av dessa kriterier: de fungerar bara på en delmängd grafer, eller så använder de inte alltid ett optimalt antal färger, eller de kör inte alltid under polynomtid.

Färga specialklasser av grafer optimalt

För bipartitgrafer eller multigrafer med maximal grad $Δ$ är det optimala antalet färger exakt $Δ$ . Cole, Ost & Schirra (2001) visade att en optimal kantfärgning av dessa grafer kan hittas i den nära linjära tidsbundna $O (m log Δ)$ , där $m$ är antalet kanter i grafen; enklare, men något långsammare, algoritmer beskrivs av Cole & Hopcroft (1982) och Alon (2003) . Algonitmen för Alon (2003) börjar med att göra inmatningsdiagrammet regelbundet, utan att öka dess grad eller öka dess storlek avsevärt, genom att slå ihop hörnpar som hör till samma sida av delningen och sedan lägga till ett litet antal ytterligare hörn och kanter . Om graden är udda hittar Alon en perfekt matchning i nära linjär tid, tilldelar den en färg och tar bort den från grafen, vilket gör att graden blir jämn. Slutligen tillämpar Alon en observation av Gabow (1976) , att val av alternerande delmängder av kanter i en Euler -rundtur i grafen delar upp den i två vanliga delgrafer, för att dela upp färgfärgningsproblemet i två mindre delproblem, och hans algoritm löser de två delproblemen rekursivt . Den totala tiden för hans algoritm är $O (m log m)$ .

För plana grafer med maximal grad $Δ \geq 7$ är det optimala antalet färger igen exakt $Δ$ . Med det starkare antagandet att $Δ \geq 9$ är det möjligt att hitta en optimal kantfärgning i linjär tid ( Cole & Kowalik 2008 ).

För d-regelbundna grafer som är pseudo-slumpmässiga i den meningen att deras adjacensmatris har näst största egenvärde (i absolut värde) högst $d 1 - ε$ , d är det optimala antalet färger ( Ferber & Jain 2018 ).

Algoritmer som använder mer än det optimala antalet färger

Misra & Gries (1992) och Gabow et al. (1985) beskriver polynomiska tidsalgoritmer för att färga vilken graf som helst med $Δ + 1$ färger, som möter gränsen som ges av Vizinges sats; se Misra & Gries kantfärgningsalgoritm .

För multigrafer presenterar Karloff & Shmoys (1987) följande algoritm som de tillskriver Eli Upfal . Gör inmatningen multigraph $G$ Eulerian genom att lägga till en ny toppunkt ansluten med en kant till varje udda graders topp, hitta en Euler-rundtur och välj en orientering för turen. Forma en tvåpartsgraf $H$ där det finns två kopior av varje toppunkt av $G$ , en på varje sida av tvåpartiet, med en kant från en toppunkt $u$ på vänster sida av tvåpartiet till en toppunkt $v$ på höger sida av tvådelen närhelst den orienterade tur har en kant från $u$ till $v$ i $G$ . Tillämpa en tvådelad graf kant färgar algoritmen till $H$ . Varje färgklass i $H$ motsvarar en uppsättning kanter i $G$ som bildar en undergraf med högsta grad två; det vill säga ett disjunkta unionen av stigar och cykler, så för varje färg klass i $H$ är det möjligt att bilda tre färgklasser i $G$ . Tiden för algoritmen begränsas av tiden till kantfärgning av en tvåpartig graf, $O (m log Δ) med$ hjälp av algoritmen för Cole, Ost & Schirra (2001) . Antalet färger som denna algoritm använder är högst nära, men inte riktigt samma som Shannons gräns för . Det kan också göras till en parallell algoritm på ett enkelt sätt. I samma papper presenterar Karloff och Shmoys också en linjär tidsalgoritm för att måla multigrafer av högsta grad tre med fyra färger (som matchar både Shannons och Vizingings gränser) som fungerar på liknande principer: deras algoritm lägger till en ny toppunkt för att göra grafen Eulerian, hittar en Euler -rundtur och väljer sedan alternerande uppsättningar kanter på turen för att dela upp grafen i två undergrafer av högsta grad två. Banorna och jämna cyklerna för varje undergraf kan färgas med två färger per delgraf. Efter detta steg innehåller varje återstående udda cykel minst en kant som kan färgas med en av de två färgerna som hör till den motsatta subgrafen. Om du tar bort denna kant från den udda cykeln lämnas en väg som kan färgas med hjälp av de två färgerna för dess undergraf. ${\ displaystyle 3 \ left \ lceil {\ frac {\ Delta} {2}} \ right \ rceil}$ ${\ displaystyle \ left \ lfloor {\ frac {3 \ Delta} {2}} \ right \ rfloor}$

En girig färgalgoritm som betraktar kanterna på en graf eller multigraf en efter en och tilldelar varje kant den första tillgängliga färgen, kan ibland använda så många som $2Δ - 1$ färger, vilket kan vara nästan dubbelt så många färger som är nödvändigt. Det har dock fördelen att det kan användas i online -algoritminställningen där inmatningsdiagrammet inte är känt i förväg; i denna inställning är dess konkurrensförhållande två, och detta är optimalt: ingen annan online -algoritm kan uppnå bättre prestanda. Men om kanterna kommer i en slumpmässig ordning och inmatningsgrafen har en grad som är åtminstone logaritmisk kan mindre konkurrensförhållanden uppnås.

Flera författare har gjort gissningar som innebär att fraktionellt kromatiskt index för valfri multigraf (ett tal som kan beräknas i polynomtid med linjär programmering ) ligger inom ett av det kromatiska indexet. Om dessa gissningar är sanna, skulle det vara möjligt att beräkna ett tal som aldrig är mer än ett avstånd från det kromatiska indexet i multigraffallet, vilket matchar vad som är känt via Vizing's sats för enkla grafer. Även om det inte är bevisat i allmänhet är dessa kända gissningar kända för att hålla när det kromatiska indexet är åtminstone , vilket kan hända för multigrafer med tillräckligt stor mångfald. ${\ displaystyle \ Delta +{\ sqrt {\ Delta /2}}}$

Exakta algoritmer

Det är enkelt att testa om en graf kan vara kantfärgad med en eller två färger, så det första otrevliga fallet med kantfärgning är att testa om en graf har en trekantig färgning. Som Kowalik (2009) visade är det möjligt att testa om en graf har en 3-kant-färgning i tiden $O (1.344 n)$ , medan man bara använder polynomutrymme. Även om denna tidsbegränsning är exponentiell, är den betydligt snabbare än en brute force -sökning över alla möjliga tilldelningar av färger till kanter. Varje tvåkopplad 3-vanlig graf med $n$ hörn har $O (2 n /2)$ 3-kant-färgningar; alla kan listas i tid $O (2 n /2)$ (något långsammare än tiden för att hitta en enda färgning); som Greg Kuperberg observerade har grafen för ett prisma över en $n /2$ -sidig polygon $Ω (2 n /2)$ färgningar (nedre istället för övre gräns), vilket visar att denna gräns är tät.

Genom att tillämpa exakta algoritmer för vertexfärgning på linjediagrammet för inmatningsdiagrammet är det möjligt att optimalt kantfärga alla diagram med $m-$ kanter, oavsett antalet färger som behövs, i tiden $2 m m O (1)$ och exponentiellt utrymme , eller i tiden $O (2.2461 m)$ och endast polynomrum ( Björklund, Husfeldt & Koivisto 2009 ).

Eftersom kantfärgning är NP-komplett även för tre färger, är det osannolikt att den är fixerad med parametrar som går att parametrisera med antalet färger. Det är dock överförbart för andra parametrar. I synnerhet visade Zhou, Nakano & Nishizeki (1996) att för grafer över trädbredden $w$ kan en optimal kantfärgning beräknas i tiden $O (nw (6 w) w (w + 1)/2)$ , en gräns som beror superexponentiellt på $w$ men endast linjärt på antalet $n$ hörn i grafen.

Nemhauser & Park (1991) formulerar kantfärgningsproblemet som ett heltalsprogram och beskriver deras erfarenhet med hjälp av en heltalsprogrammeringslösare till kantfärgdiagram. De utförde dock ingen komplexitetsanalys av deras algoritm.

Ytterligare fastigheter

Den unikt 3-färgbara generaliserade Petersen-grafen

G (9,2)

. En av dess tre färgklasser visas med de ljusa kanterna och de andra två kan hittas antingen genom att rotera de ljusa kanterna med 40 ° i varje riktning eller genom att dela den mörka Hamiltonian -cykeln i alternerande kanter.

En graf unikt $k$ -edge-PLAUSIBEL om det bara finns ett sätt att dela upp kanterna i $k$ färgklasser och strunta i $k!$ möjliga permutationer av färgerna. För $k \neq 3$ är de enda unika $k$ -kantfärgbara graferna vägar, cykler och stjärnor , men för $k = 3 kan$ andra grafer också vara unikt $k$ -kantfärgbara. Varje unikt 3-kantfärgbar graf har exakt tre Hamiltonian-cykler (bildas genom att ta bort en av de tre färgklasserna) men det finns 3-regelbundna grafer som har tre Hamiltonian-cykler och inte är unikt 3-färgbara, till exempel de generaliserade Petersen-graferna $G (6 n + 3, 2)$ för $n \geq 2$ . Den enda kända icke-plana unika trefärgbara grafen är den generaliserade Petersen-grafen $G (9,2)$ , och det har antagits att inga andra existerar.

Den kompletta bipartitdiagrammet K _3,3 med var sin färgklass ritad som parallella linjesegment på distinkta linjer.

Folkman & Fulkerson (1969) undersökte de icke-ökande sekvenserna av siffrorna $m 1, m 2, m 3, ...$ med egenskapen att det finns en korrekt kantfärgning av en given graf $G$ med $m 1$ kanter av den första färgen, $m 2$ kanter av den andra färgen, etc. De observerade att om en sekvens $P$ är genomförbar i denna mening och är större i lexikografisk ordning än en sekvens $Q$ med samma summa, då är $Q$ också genomförbart. För, om $P > Q$ i lexikografisk ordning, då kan $P$ omvandlas till $Q$ genom en sekvens av steg, som var och en reducerar ett av talen $m i$ med en enhet och ökar ytterligare ett senare nummer $m j$ med $i < j$ med en enhet . När det gäller kantfärgningar, utgående från en färgning som realiserar $P$ , kan vart och ett av samma steg utföras genom att byta färgerna $i$ och $j$ på en Kempe -kedja , en maximal väg för kanter som växlar mellan de två färgerna. I synnerhet har varje graf en rättvis kantfärgning, en kantfärgning med ett optimalt antal färger där varannan färgklass skiljer sig åt i storlek med högst en enhet.

Den De Bruijn-Erdős sats kan användas för att överföra många kantfärgningsegenskaperna hos ändliga grafer till oändliga grafer . Exempelvis generaliserar Shannons och Vizingings satser graden av en graf till dess kromatiska index direkt till oändliga grafer.

Richter (2011) överväger problemet med att hitta en grafritning av en given kubikgraf med egenskaperna att alla kanterna i ritningen har en av tre olika lutningar och att inga två kanter ligger på samma linje som varandra. Om en sådan ritning finns, kan kanternas sluttningar helt klart användas som färger i en trekantig färgning av grafen. Till exempel representerar ritningen av användningsdiagrammet $K 3,3$ som kanterna och långa diagonalerna på en vanlig sexkant en trekantig färgning av grafen på detta sätt. Som Richter visar har en 3-vanlig enkel bipartitgraf, med en given Tait-färgning, en ritning av denna typ som representerar den givna färgen om och bara om grafen är 3-kant-ansluten . För en icke-tvåpartig graf är villkoret lite mer komplicerat: en given färgning kan representeras av en ritning om det tvåpartiga omslaget på grafen är 3-kantanslutet och om radering av några monokromatiska kanter leder till en subgraf som fortfarande är icke-bipartit. Dessa villkor kan alla testas enkelt på polynomtid; Problemet med att testa om ett 4-kantigt färgat 4-regelbundet diagram har en ritning med kanter på fyra lutningar, som representerar färgerna i lutningar, är dock komplett för den existentiella teorin om realerna , en komplexitetsklass minst lika svår som är NP-komplett.

Förutom att det är relaterat till den maximala graden och det maximala matchningsnumret för en graf, är det kromatiska indexet nära besläktat med den linjära arboriciteten $la (G)$ för en graf $G$ , det minsta antalet linjära skogar (disjoint fackföreningar av vägar) som grafens kanter kan vara partitionerade. En matchning är en speciell typ av linjär skog, och i andra riktningen kan vilken linjär skog som helst vara tvåkantad, så för varje $G$ följer det att $la (G) \leq χ ' (G) \leq 2 la (G)$ . Akiyamas gissning (uppkallad efter Jin Akiyama ) säger att , varifrån det skulle följa starkare än $2 la ($ $G$ $) - 2 \leq χ ' ($ $G$ $) \leq 2 la ($ $G$ $)$ . För grafer med högsta grad tre är $la ($ $G$ $)$ alltid exakt två, så i detta fall $matchar$ gränsen $χ ' ($ $G$ $) \leq 2 la ($ $G$ $)$ gränsen som ges av Vizinges sats. ${\ displaystyle \ mathop {\ mathrm {la}} (G) \ leq \ left \ lceil {\ frac {\ Delta +1} {2}} \ right \ rceil}$

Andra typer

En uppdelning av den fullständiga bipartitdiagrammet K _4,4 i tre skogar, som visar att den har arboricitet tre.

Den Thue antal av ett diagram är antalet färger som krävs i en kant färgämnen uppfylla den starkare kravet att, i varje jämn längd bana, de första och andra halvorna av banan bildar olika sekvenser av färger.

Den arboricity av ett diagram är det minsta antalet färger som krävs så att kanterna av varje färg har några cykler (snarare än i standard kanten färgning problem, som inte har några intilliggande par av kanter). Det vill säga det är det minsta antalet skogar som kanterna på grafen kan delas in i. Till skillnad från det kromatiska indexet kan arboriciteten hos en graf beräknas under polynomtid.

Lista kantfärgning är ett problem där man får en graf där varje kant är associerad med en lista med färger och måste hitta en korrekt kantfärgning där färgen på varje kant dras från den kantens lista. Listkromatiskt index för en graf $G$ är det minsta talet $k$ med egenskapen att, oavsett hur man väljer listor med färger för kanterna, så länge varje kant har minst $k$ färger i listan, så är en färgning garanterad att vara möjligt. Listans kromatiska index är således alltid minst lika stort som det kromatiska indexet. Den Dinitz gissningar på slutförandet av partiella latinska kvadrater kan omformuleras som påståendet att listan kanten kromatiska antal av kompletta tvådelade grafen $K n, n$ är lika med dess kant kromatisk nummer $n$ . Galvin (1995) löste gissningen genom att mer allmänt bevisa att i varje tvåpartig graf är det kromatiska indexet och listkromatiska index lika. Jämlikheten mellan det kromatiska indexet och det listiga kromatiska indexet har tänkts att gälla, ännu mer allmänt, för godtyckliga multigrafer utan självslingor; denna gissning förblir öppen.

Många andra vanligt studerade variationer av vertexfärgning har också utökats till kantfärgningar. Till exempel är komplett kantfärgning kantfärgningsvarianten för komplett färgning , en riktig kantfärgning där varje par färger måste representeras av minst ett par angränsande kanter och där målet är att maximera det totala antalet färger . Stark kantfärgning är kantfärgningsvarianten av stark färgning , en kantfärgning där varannan kant med angränsande ändpunkter måste ha olika färger. Stark kantfärgning har applikationer i kanaltilldelningssystem för trådlösa nätverk .

Acyklisk kantfärgning är kantfärgningsvarianten av acyklisk färgning , en kantfärgning för vilken varannan färgklass bildar en acyklisk subgraf (det vill säga en skog). Det acykliska kromatiska indexet för en graf , betecknat med , är det minsta antal färger som behövs för att få en korrekt acyklisk kantfärgning av . Det har gissats att , var är den maximala graden av . För närvarande är den mest kända gränsen . Problemet blir lättare när det har stor omkrets . Mer specifikt finns det en konstant sådan att om omkretsen är åtminstone , då . Ett liknande resultat är att det för alla finns ett sådant att om det har omkrets åtminstone , då . ${\ displaystyle G}$ ${\ displaystyle a '(G)}$ ${\ displaystyle G}$ ${\ displaystyle a '(G) \ leq \ Delta +2}$ ${\ displaystyle \ Delta}$ ${\ displaystyle G}$ ${\ displaystyle a '(G) \ leq \ lceil 3.74 (\ Delta -1) \ rceil}$ ${\ displaystyle G}$ ${\ displaystyle c}$ ${\ displaystyle G}$ ${\ displaystyle c \ Delta \ log \ Delta}$ ${\ displaystyle a '(G) \ leq \ Delta +2}$ ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle g}$ ${\ displaystyle G}$ ${\ displaystyle g}$ ${\ displaystyle a '(G) \ leq (1+ \ epsilon) \ Delta}$

Eppstein (2013) studerade 3-kant-färgningar av kubikgrafer med den extra egenskapen att inga två bikromatiska cykler delar mer än en enda kant med varandra. Han visade att förekomsten av en sådan färgning motsvarar förekomsten av en ritning av grafen på ett tredimensionellt heltalsgaller, med kanter parallella med koordinataxlarna och varje axelparallell linje som innehåller högst två hörn. Men som det vanliga 3-kantsproblemet med färgning är det helt enkelt att hitta en färg av denna typ.

Totalfärgning är en form av färgning som kombinerar hörn- och kantfärgning genom att kräva att både hörn och kanter ska färgas. Varje infallande par i en toppunkt och en kant, eller en kant och en kant, måste ha olika färger, liksom alla två intilliggande hörn. Man har gissat (kombinerar Vizinges sats och Brooks sats ) att varje graf har en total färgning där antalet färger högst är den maximala graden plus två, men detta förblir obevisat.

Om en tre-regelbunden graf på en yta är 3-kant-färgad, bildar dess dubbla diagram en triangulering av ytan som också är kantfärgad (även om den inte är i allmänhet korrekt kantfärgad) på ett sådant sätt att varje triangel har en kanten på varje färg. Andra färgningar och orienteringar av trianguleringar, med andra lokala begränsningar för hur färgerna är ordnade vid trianguleringens hörn eller ytor, kan användas för att koda flera typer av geometriska objekt. Exempelvis kan rektangulära indelningar (partitioner av en rektangulär indelning i mindre rektanglar, med tre rektanglar som möts vid varje hörn) beskrivas kombinatoriskt med en "vanlig märkning", en tvåfärgning av kanterna på en triangulering dubbel till underavdelningen, med begränsningen att kanterna som infaller till varje hörn bildar fyra sammanhängande undersekvenser, inom vilka var och en av färgerna är desamma. Denna märkning är dubbel till en färgning av själva den rektangulära indelningen där de vertikala kanterna har en färg och de horisontella kanterna har den andra färgen. Liknande lokala begränsningar i den ordning i vilken färgade kanter kan uppträda runt en hörnpunkt kan också användas för att koda rätlinjiga rutnätinbäddningar av plana grafer och tredimensionella polyeder med axelparallell sidor. För var och en av dessa tre typer av vanliga märkningar utgör uppsättningen vanliga märkningar av ett fast diagram ett distributivt gitter som kan användas för att snabbt lista alla geometriska strukturer baserade på samma graf (t.ex. alla axelparallell polyeder med samma skelett ) eller för att hitta strukturer som uppfyller ytterligare begränsningar.

En deterministisk ändlig automat kan tolkas som en riktad graf där varje hörn har samma ut -grad $d$ , och där kanterna är $d$ -färgade på ett sådant sätt att varannan kant med samma källpunkt har olika färger. Den väg färgning problem är problemet med kant färga en riktad graf med enhetliga ut-grader, på ett sådant sätt att den resulterande automat har en synkroniseringsord . Trahtman (2009) löste problemet med vägfärgning genom att bevisa att en sådan färgning kan hittas när den givna grafen är starkt ansluten och periodisk .

Ramseys sats gäller problemet med $k$ -färgning av kanterna på en stor komplett graf $K n$ för att undvika att skapa monokromatiska fullständiga undergrafer $K s$ av viss storlek $s$ . Enligt den sats, det finns ett antal $R k (s)$ så att, närhelst $n \geq R (s)$ , inte är möjligt en sådan färg. Exempelvis $R 2 (3) = 6$ , som är, om kanterna av grafen $K 6$ är 2-färgad, kommer det alltid att vara en monokromatisk triangel.

En bana i en kantfärgad graf sägs vara en regnbågsbana om ingen färg upprepas på den. En graf sägs vara regnbågsfärgad om det finns en regnbågsbana mellan två hörnpar. En kantfärgning av en graf G med färger 1.. . t är ett intervall t färgning om alla färger används, och färgerna på kanterna som infaller till varje toppunkt av G är distinkta och bildar ett intervall av heltal.

Ansökningar

Kantfärgningar av kompletta grafer kan användas för att schemalägga en runda-turnering i så få omgångar som möjligt så att varje par tävlande spelar varandra i en av omgångarna; i denna applikation motsvarar kurvens hörn de tävlande i turneringen, kanterna motsvarar spel och kantfärgerna motsvarar de rundor där spelen spelas. Liknande färgtekniker kan också användas för att schemalägga andra sportpar som inte är all-play-all; till exempel i National Football League bestäms paren som ska spela mot varandra under ett visst år, baserat på lagens poster från föregående år, och sedan appliceras en kantfärgningsalgoritm på grafen som bildas av uppsättning parningar för att tilldela spel till helgerna där de spelas. För den här applikationen innebär Vizinges sats att oavsett vilken uppsättning parningar som väljs (så länge inga lag spelar varandra två gånger under samma säsong) är det alltid möjligt att hitta ett schema som använder högst en helg till än det finns spel per lag.

Schemaläggning i öppna butiker är ett problem med schemaläggning av produktionsprocesser , där det finns en uppsättning objekt som ska tillverkas, varje objekt har en uppsättning uppgifter som ska utföras på det (i valfri ordning) och varje uppgift måste utföras på en specifik maskin, vilket förhindrar att alla andra uppgifter som kräver att samma maskin utförs samtidigt. Om alla uppgifter har samma längd, kan detta problem formaliseras som en av kantfärgning av en tvåpartsmultigraf, där hörnen på ena sidan av delningen representerar föremålen som ska tillverkas, hörnen på den andra sidan av tvåpartiet representerar tillverkningsmaskinerna, kanterna representerar uppgifter som måste utföras och färgerna representerar tidssteg där varje uppgift kan utföras. Eftersom tvåpartskantfärgning kan utföras under polynomtid gäller samma sak för detta begränsade fall av schemaläggning i öppna butiker.

Gandham, Dawande & Prakash (2005) studerar problemet med schemaläggning av länkar för kommunikationsprotokoll för tidsdelning med flera åtkomstnät på sensornätverk som en variant av kantfärgning. I detta problem måste man välja tidsluckor för kanterna på ett trådlöst kommunikationsnät så att varje nod i nätverket kan kommunicera med varje angränsande nod utan störningar. Att använda en stark kantfärgning (och använda två tidsluckor för varje kantfärg, en för varje riktning) skulle lösa problemet men kan använda fler tidsluckor än nödvändigt. Istället söker de en färgning av den riktade grafen som bildas genom att fördubbla varje oriktad kant i nätverket, med egenskapen att varje riktad kant $uv$ har en annan färg från kanterna som går ut från $v$ och från grannarna till $v$ . De föreslår en heurist för detta problem baserat på en distribuerad algoritm för $(Δ + 1)$ -färgning tillsammans med en efterbehandlingsfas som omplanerar kanter som kan störa varandra.

I fiberoptiska kommunikations , den bana färgning är problemet problemet med att tilldela färger (frekvenser av ljus) till par av noder som önskar kommunicera med varandra, och vägar genom ett fiberoptiskt kommunikationsnät för varje par, med förbehåll för begränsningen att inga två vägar som delar ett segment av fiber använder samma frekvens som varandra. Vägar som passerar genom samma kommunikationsomkopplare men inte genom något fiberparti får använda samma frekvens. När kommunikationsnätet är anordnat som ett stjärnnätverk , med en enda central switch kopplad med separata fibrer till var och en av noderna, kan banfärgningsproblemet modelleras exakt som ett problem med kantfärgning av en graf eller multigraf, där de kommunicerade noderna bilda grafens hörn, par av noder som vill kommunicera från grafkanterna och de frekvenser som kan användas för varje par bildar färgerna på kantfärgningsproblemet. För kommunikationsnätverk med en mer allmän trädtopologi kan lokala vägfärglösningar för stjärnnätverk som definieras av varje switch i nätverket lappas ihop för att bilda en enda global lösning.

Öppna problem

Jensen & Toft (1995) listar 23 öppna problem med kantfärgning. De inkluderar:

Gissningen från Goldberg (1973) att det kromatiska indexet och fraktionsindexet ligger inom varandra, vilket skulle göra det möjligt att approximera det kromatiska indexet inom en färg på polynomtid.
Flera gissningar av Jakobsen och andra om strukturen för kritiska grafer för kantfärgning, grafer i klass 2 så att varje undergraf antingen har mindre högsta grad eller är av klass 1. Jakobsen gissade ursprungligen att alla kritiska grafer har ett udda antal hörn, men detta motbevisades så småningom. Flera andra gissningar som försvagar denna, eller begränsar antalet hörn för kritiska grafer och kritiska multigrafer, förblir öppna.
Vizing problem med att klassificera de maximala grader som är möjliga för klass 2 plana grafer.
Den överfulla subgrafgisslan från AJW Hilton, som anger att grafer med grad minst $n /3$ antingen är av klass 1 eller innehåller en subgraf med samma grad $Δ$ som originalgrafen, och med ett udda antal $k$ hörnor, så att talet av kanterna i subgrafen är större än $Δ (k- 1)/2$ , och en liknande gissning av Herbert Grötzsch och Paul Seymour angående plana grafer istället för grafer med hög grad.
En gissning av Amanda Chetwynd och Anthony Hilton (möjligen att gå tillbaka tidigare till Gabriel Andrew Diracs arbete ) att vanliga grafer med ett jämnt antal $n$ hörn och med minst $n /2$ är av klass 1.
En gissning av Claude Berge och DR Fulkerson om att de 6-regelbundna multigraferna som bildas genom att fördubbla varje kant på en brolös 3-vanlig enkel graf kan vara kantfärgade med sex färger.
En gissning av Fiorini och Wilson om att varje triangelfritt plan diagram, annat än klo K _1,3 , inte är unikt 3-kant-färgbart .
En 2012 gissning att om $G$ är en $d$ -regular plant Multigraph, då $G$ vill säga $d$ -edge-PLAUSIBEL om och endast om $G$ är märkligt $d$ -edge-ansluten. Denna gissning är en generalisering av satsen med fyra färger , som uppstår vid $d$ = 3. Maria Chudnovsky , Katherine Edwards och Paul Seymour bevisade att en 8-regeln plan multigraf har ett kantkromatiskt tal på 8.

Anteckningar

Referenser

Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), "Täcker och packar i grafer. III. Cykliska och acykliska invarianter", Mathematica Slovaca , 30 (4): 405–417, MR 0595302.
Alon, Noga (2003), "En enkel algoritm för kantfärgning av tvåpartsmultigrafer", Information Processing Letters , 85 (6): 301–302, doi : 10.1016/S0020-0190 (02) 00446-5 , MR 1956451.
Alon, Noga ; Sudakov, Benny; Zaks, Ayal (2001), "Acyclic edge colourings of graphs", Journal of Graph Theory , 37 (3): 157–167, doi : 10.1002/jgt.1010 , MR 1837021.
Andersen, Lars Døvling (1977), "On edge-colourings of graphs", Mathematica Scandinavica , 40 (2): 161–175, doi : 10.7146/math.scand.a-11685 , MR 0465922. Som citerat av Chen, Yu & Zang (2011) .
Appel, K .; Haken, W. (1976), "Every planar map is four colourable", Bulletin of the American Mathematical Society , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR 0424602.
Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), "En 1,43-konkurrenskraftig online-grafkantfärgningsalgoritm i modellen för slumpmässig ordning", Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) , s. 31–39.
Bar-Noy, Amotz; Motwani, Rajeev ; Naor, Joseph (1992), "Den giriga algoritmen är optimal för onlinekantfärgning", Information Processing Letters , 44 (5): 251–253, doi : 10.1016/0020-0190 (92) 90209-E.
Barrett, CL; Istrate, G .; Kumar, VSA; Marathe, MV; Thite, S .; Thulasidasan, S. (2006), "Stark kantfärgning för kanaltilldelning i trådlösa radionät", Proc. Fjärde årliga IEEE International Conference on Pervasive Computing Workshops (PerCom Workshops 2006) , sid. 106, doi : 10.1109/PERCOMW.2006.129 , ISBN 0-7695-2520-2, S2CID 5797236.
Biggs, Norman (1972), Guy, Richard K. (red.), "An edge-coloring problem", Research Problems, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307/2318076 , JSTOR 2318076.
Biggs, Norman (1979), "Some odd graph theory", andra internationella konferensen om kombinerande matematik, Annals of the New York Academy of Sciences , 319 (1): 71–81, Bibcode : 1979NYASA.319 ... 71B , doi : 10.1111/j.1749-6632.1979.tb32775.x , S2CID 84995087.
Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), "Set partitioning via inclusion-exclusion" (PDF) , SIAM Journal on Computing , 39 (2): 546–563, doi : 10.1137/070683933 , MR 2529771.
Bosák, Juraj (1972), "Chromatic index of endelige och oändliga grafer", Czechoslovak Mathematical Journal , 22 (97): 272–290, doi : 10.21136/CMJ.1972.101098 , MR 0309777.
Bosák, Juraj; Nešetřil, Jaroslav (1976), "Komplett och pseudokomplett färgläggning av en graf", Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, MR 0439672.
Cai, XS; Perarnau, G .; Reed, BA ; Watt, AB (2014), "Acykliska kantfärgningar av grafer med stor omkrets", Random Structures & Algorithms , 50 (4): 511-533, arXiv : 1411,3047 , doi : 10.1002 / rsa.20695 , S2CID 7.727.097.
Burke, E .; De Werra, D .; Kingston, J. (2004), "5.6.5 Sports Timetapping" , i JL, Gross; Yellen, J. (red.), Handbook of Graph Theory , CRC Press, sid. 462, ISBN 978-1-58488-090-5.
Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), "Approximating the chromatic index of multigraphs", Journal of Combinatorial Optimization , 21 (2): 219–246, doi : 10.1007/s10878-009-9232-y , MR 2770056 , S2CID 169162.
Chudnovsky, Maria ; Edwards, Katherine; Seymour, Paul (2012), "Kantfärgning av åtta regelbundna plana grafer", arXiv : 1209.1176 [ cs.DM ].
Cole, Richard; Hopcroft, John (1982), "On edge coloring bipartite graphs", SIAM Journal on Computing , 11 (3): 540–546, doi : 10.1137/0211043 , hdl : 1813/6283 , MR 0664720.
Cole, Richard; Kowalik, Łukasz (2008), "New linjära-tid algoritmer för kantfärgande plana grafer", Algorithmica , 50 (3): 351-368, doi : 10,1007 / s00453-007-9044-3 , MR 2.366.985 , S2CID 7.692.895.
Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), "Kantfärgande tvåpartsmultigrafer i $O (E log D)$ tid", Combinatorica , 21 (1): 5–12, doi : 10.1007/s004930170002 , MR 1805711 , S2CID 522145.
Cranston, Daniel W. (2006), "Stark kantfärgning av grafer med maximal grad 4 med 22 färger", Diskret matematik , 306 (21): 2772–2778, arXiv : math/0601623 , Bibcode : 2006math .... ..1623C , doi : 10.1016/j.disc.2006.03.053 , MR 2264374 , S2CID 1097275.
Eppstein, David (2013), "The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing", Journal of Graph Algorithms and Applications , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155/jgaa.00283 , S2CID 2716392.
Eppstein, David (2010), "Regelbundna märkningar och geometriska strukturer", Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010) (PDF) , University of Manitoba, arXiv : 1007.0221 , Bibcode : 2010arXiv1007.0221E.
Erdős, Paul ; Wilson, Robin J. (1977), "Notering om det kromatiska indexet för nästan alla grafer" (PDF) , Journal of Combinatorial Theory , Series B, 23 (2–3): 255–257, doi : 10.1016/0095-8956 (77) 90039-9.
Erlebach, Thomas; Jansen, Klaus (2001), "The complexity of path coloring and call scheduling", Theoretical Computer Science , 255 (1–2): 33–50, doi : 10.1016/S0304-3975 (99) 00152-8 , MR 1819065.
Ferber, Asaf; Jain, Vishesh (2018), "1-faktorisering av pseudoslumpgrafer", arXiv : 1803.10361 [ math.CO ].
Fiamčik, J. (1978), "Den acykliska kromatiska klassen i en graf", Math. Slovaca , 28 : 139–145.
Fiorini, S .; Wilson, Robin James (1977), Edge-colourings of graphs , Research Notes in Mathematics, 16 , London: Pitman, ISBN 0-273-01129-4, MR 0543798.
Folkman, Jon ; Fulkerson, DR (1969), "Edge colourings in bipartite graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, s. 561–577, MR 0262112.
Fouquet, J.-L .; Jolivet, J.-L. (1983), "Starka kantfärgningar av grafer och applikationer till multi- $k-$ goner", Ars Combinatoria , 16 (A): 141–150, MR 0737086.
Frieze, Alan M .; Krivelevich, Michael; Sudakov, Benny (2005), "Det starka kromatiska indexet för slumpmässiga grafer" (PDF) , SIAM Journal on Discrete Mathematics , 19 (3): 719–727 (elektronisk), doi : 10.1137/S0895480104445757 , MR 2191290.
Gabow, Harold N. (1976), "Using Euler partitions to edge color bipartite multigraphs", International Journal of Computer and Information Sciences , 5 (4): 345–355, doi : 10.1007/BF00998632 , MR 0422081 , S2CID 36331285.
Gabow, Harold N .; Nishizeki, Takao ; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algoritmer för kantfärgningsgrafer , Tech. Rapportera TRECIS-8501, Tohoku University.
Gabow, Harold N .; Westermann, Herbert H. (1992), "Skogar, ramar och spel: algoritmer för matroid summor och applikationer", Algorithmica , 7 (5-6): 465-497, doi : 10,1007 / BF01758774 , MR 1.154.585 , S2CID 40.358.357.
Galvin, F. (1995), "The list kromatic index of a bipartite multigraph", Journal of Combinatorial Theory , Series B, 63 (1): 153–158, doi : 10.1006/jctb.1995.1011.
Gandham, S .; Dawande, M .; Prakash, R. (2005), "Länkplanering i sensornätverk: distribuerad kantfärgning återbesökt", Proc. 24: e INFOCOM , 4 , s. 2492–2501, doi : 10.1109/INFCOM.2005.1498534 , ISBN 0-7803-8968-9, S2CID 8085139.
Giotis, I .; Kirousis, L .; Psaromiligkos, KI; Thilikos, DM (2015), "On the algorithmic Lovász Local Lemma and acyclic edge coloring", Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) , sid. 16, doi : 10.1137/1.9781611973761.2 , ISBN 978-1-61197-376-1.
Goldberg, MK (1973), "Multigraf med ett kromatiskt index som är nästan maximalt", Diskret. Analiz. (23): 3–7, 72, MR 0354429. Som citerat av Chen, Yu & Zang (2011) .
Habib, M .; Péroche, B. (1982), "Några problem om linjär arboricitet", Diskret matematik , 41 (2): 219–220, doi : 10.1016/0012-365X (82) 90209-6 , MR 0676882.
Holyer, Ian (1981), "The NP-completeness of edge-coloring", SIAM Journal on Computing , 10 (4): 718–720, doi : 10.1137/0210055.
Horák, Peter; Niepel, Ľudovít (1982), "Ett kort bevis på en linjär arboricitetsteorem för kubikgrafer", Acta Mathematica Universitatis Comenianae , 40/41: 275–277, MR 0686983.
Jensen, Tommy R .; Toft, Bjarne (1995), Graph Coloring Problems , New York: Wiley-Interscience, ISBN 0-471-02865-7.
Karloff, Howard J .; Shmoys, David B. (1987), "Effektiva parallella algoritmer för problem med kantfärgning", Journal of Algorithms , 8 (1): 39–52, doi : 10.1016/0196-6774 (87) 90026-5 , MR 0875324.
Konig, D. (1916), "Über graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre" , Mathematische Annalen , 77 (4): 453-465, doi : 10,1007 / BF01456961 , HDL : 10338.dmlcz / 127.635 , S2CID 121.097.364 , arkiveras från originalet 2015-01-19 , hämtat 2013-09-30.
Kowalik, Łukasz (2009), "Förbättrad kantfärgning med tre färger", Teoretisk datavetenskap , 410 (38–40): 3733–3742, doi : 10.1016/j.tcs.2009.05.005 , MR 2553326.
Mahdian, Mohammad (2002), "On the computational complexity of strong edge coloring", Diskret tillämpad matematik , 118 (3): 239–248, doi : 10.1016/S0166-218X (01) 00237-2 , MR 1892971.
Meredith, Guy HJ; Lloyd, E. Keith (1973), "The footballers of Croam", Journal of Combinatorial Theory , Series B, 15 (2): 161–166, doi : 10.1016/0095-8956 (73) 90016-6.
Misra, J .; Gries, David (1992), "A constructive proof of Vizing's Theorem", Information Processing Letters , 41 (3): 131–133, doi : 10.1016/0020-0190 (92) 90041-S.
Muthu, Rahul; Narayanan, N .; Subramanian, CR (2007), "Förbättrade gränser för acyklisk kantfärgning", Diskret matematik , 307 (23): 3063–3069, doi : 10.1016/j.disc.2007.03.006 , MR 2371078.
Nash-Williams, C. St. JA (1964), "Nedbrytning av ändliga grafer till skogar", Journal of the London Mathematical Society , Second Series, 39 : 12, doi : 10.1112/jlms/s1-39.1.12 , MR 0161333
Nemhauser, George L .; Park, Sungsoo (1991), "A polyhedral approach to edge coloring", Operations Research Letters , 10 (6): 315–322, doi : 10.1016/0167-6377 (91) 90003-8 , MR 1128970.
Richter, David A. (2011), "How to draw a Tait-colourable graph", i Brandes, Ulrik ; Cornelsen, Sabine (red.), Proc. 18th International Symposium on Graph Drawing (GD 2010) , Lecture Notes in Computer Science, 6502 , Springer-Verlag, s. 353–364, doi : 10.1007/978-3-642-18469-7_32 , ISBN 978-3-642-18468-0.
Sanders, Daniel P .; Zhao, Yue (2001), "Plana grafer med högsta grad sju är klass I", Journal of Combinatorial Theory , Series B, 83 (2): 201–212, doi : 10.1006/jctb.2001.2047.
Seymour, PD (1979), "On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte", Proceedings of the London Mathematical Society , Third Series, 38 (3): 423–460, doi : 10.1112/plms/s3-38.3 .423 , MR 0532981.
Schwenk, Allen J. (1989), "Enumeration of Hamiltonian cycles in some generalized Petersen graphs", Journal of Combinatorial Theory , Series B, 47 (1): 53–59, doi : 10.1016/0095-8956 (89) 90064- 6 , MR 1007713.
Shannon, Claude E. (1949), "Ett teorem om att färga linjerna i ett nätverk", J. Math. Physics , 28 (1–4): 148–151, doi : 10.1002/sapm1949281148 , hdl : 10338.dmlcz/101098 , MR 0030203.
Skiena, Steven S. (2008), "16.8 Edge Coloring", The Algorithm Design Manual (2nd ed.), Springer-Verlag, s. 548–550, doi : 10.1007/978-1-84800-070-4_16 , ISBN 978-1-84800-069-8. Se även webbplatsen för detta avsnitt av boken i Stony Brook Algorithm Repository.
Soifer, Alexander (2008), The Mathematical Coloring Book , Springer-Verlag, ISBN 978-0-387-74640-1.
Tait, PG (1880), "Anmärkningar om färgerna på kartor", Proc. R. Soc. Edinburgh , 10 : 729, doi : 10.1017/S0370164600044643.
Trahtman, Avraham N. (2009), "The road coloring problem", Israel Journal of Mathematics , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007/s11856-009-0062-5 , S2CID 515742.
Vizing, VG (1964), "På en uppskattning av den kromatiska klassen av en p -graf", Diskret. Analiz. , 3 : 25–30, MR 0180505.
Vizing, VG (1965), "Kritiska grafer med given kromatisk klass", Metody Diskret. Analiz. , 5 : 9–17. (På ryska.)
Williamson, DP ; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Short shop schedules", Operations Research , 45 (2): 288–294, doi : 10.1287/opre.45.2.288 , JSTOR 171745 , MR 1644998.
Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), "Edge -coloring partial $k$ -trees", Journal of Algorithms , 21 (3): 598–617, doi : 10.1006/jagm.1996.0061 , MR 1417666.

Languages

In other projects