Svag färgning
I grafteorin är en svag färgning ett specialfall av en grafmärkning . En svag k -färgning av en graf G = ( V , E ) tilldelar en färg c ( v ) ∈ {1, 2, ..., k } till varje vertex v ∈ V , så att varje icke- isolerad vertex ligger intill till minst en vertex med annan färg. I notation, för varje oisolerad v ∈ V , finns det en vertex u ∈ V med { u , v } ∈ E och c ( u ) ≠ c ( v ) .
Figuren till höger visar en svag 2-färgning av en graf. Varje mörk vertex (färg 1) ligger intill minst en ljus vertex (färg 2) och vice versa.
Egenskaper
En grafvertexfärgning är en svag färgning, men inte nödvändigtvis vice versa.
Varje graf har en svag 2-färgning. Figuren till höger illustrerar en enkel algoritm för att konstruera en svag 2-färgning i en godtycklig graf. Del (a) visar den ursprungliga grafen. Del (b) visar ett sökträd med bredd-först av samma graf. Del (c) visar hur man färgar trädet: med början från roten färgas trädets lager omväxlande med färgerna 1 (mörk) och 2 (ljus).
Om det inte finns någon isolerad vertex i grafen G , så bestämmer en svag 2-färgning en domatisk partition : uppsättningen av noder med c ( v ) = 1 är en dominerande uppsättning , och uppsättningen av noder med c ( v ) = 2 är en annan dominerande uppsättning.
Ansökningar
Historiskt sett fungerade svag färgning som det första icke-triviala exemplet på ett grafproblem som kan lösas med en lokal algoritm (en distribuerad algoritm som körs i ett konstant antal synkrona kommunikationsrundor). Mer exakt, om graden av varje nod är udda och avgränsad av en konstant, så finns det en konstant-tidsfördelad algoritm för svag 2-färgning.
Detta skiljer sig från (icke-svag) vertexfärgning : det finns ingen konstant-tidsfördelad algoritm för vertexfärgning; de bästa möjliga algoritmerna (för att hitta en minimal men inte nödvändigtvis minsta färg) kräver O ( log * | V |) kommunikationsrundor. Här log * x den itererade logaritmen av x .