I grafteori og i algoritmik , farvning kanterne af en graf består i at tildele hver kant en farve, så man undgår, at to kanter har en fælles ende er af samme farve.
Figuren overfor er et eksempel på korrekt kantfarvning. Det kontrolleres faktisk, at intet toppunkt er fælles for to kanter af samme farve. Bemærk, at det her ikke ville have været muligt at farve kanterne på grafen med kun to farver.
Nævnt uden yderligere præcision betegner udtrykket "farvning af kanterne på en graf" det faktum, at hver kant tildeles en farve, så to tilstødende kanter (det vil sige at have en fælles ende) ikke altid har den samme farve. (Det er en dobbelt forestilling om farvning af hjørnerne i en graf .)
Det mindste antal farver, der er nødvendigt for at opnå farvning af kanterne i en graf G , kaldes det kromatiske indeks for G eller det kromatiske antal af kanterne af G og bemærkes χ ′ ( G ) eller undertiden χ 1 ( G ). Det bør ikke forveksles med det kromatiske antal (af hjørner) af G , bemærket χ ( G ).
Hvis Δ ( G ) er den maksimale grad af G og μ ( G ) dens mangfoldighed (det maksimale antal kanter pr. Par af hjørner), så:
Som nævnt ovenfor er χ ′ ( G ) altid lig med Δ ( G ) eller til Δ ( G ) + 1. G siges at være af klasse 1 i det første tilfælde og af klasse 2 i det andet.
I 1981 beviste Holyer, at det er et NP-komplet problem at bestemme, om en simpel graf tilhører den ene eller den anden af disse to klasser . I nogle særlige tilfælde er der dog regler for en hurtig afslutning.
For eksempel fastslog Vizing , at en simpel plan graf med maksimal grad mindst lig med 8 altid er af klasse 1 og formodede, at den var den samme for en maksimal grad svarende til 6 eller 7 (vi kender enkle grafer planer med maksimal grad 2 , 3, 4 eller 5 og klasse 2). Sanders (en) og Zhao beviste sagen Δ ( G ) = 7 i hans formodning.
Denne formodning finder anvendelse i den samlede farve (en) .
Farvning af kanterne på fulde grafer kan bruges til at programmere en allround-turnering i så få runder som muligt, så hvert par af konkurrenter konkurrerer mod hinanden i en af runderne. I denne applikation svarer grafens hjørner til turneringens konkurrenter, kanterne svarer til spillet, og farven på kanterne svarer til de runder, hvor spillene spilles.
En anden anvendelse kan være planlægningen af fremstillingen af et sæt objekter med den begrænsning, at hver fremstillingsopgave skal udføres på en bestemt maskine, hvilket forhindrer enhver anden opgave, der kræver, at den samme maskine udføres på samme tid. Hvis alle opgaverne har samme varighed, kan dette problem formaliseres som farvning af en bipartit multigraf, hvor hjørnerne på den ene side af bipartitionen repræsenterer de objekter, der skal fremstilles, hjørnerne på den anden side af bipartitionerne repræsenterer fremstillingen maskiner, kanterne repræsenterer de opgaver, der skal udføres, og farverne repræsenterer de tidsintervaller, hvor hver opgave kan udføres.