Chromatische veelterm

De chromatische veelterm $\chi (G,\lambda )$ van een graaf $G$ geeft het aantal mogelijke geldige knopenkleuringen met $\lambda$ kleuren, dit is het aantal kleuringen van de knopen van de graaf zodanig dat twee knopen die door een kant verbonden zijn steeds een andere kleur hebben. Het is niet nodig dat alle $\lambda$ kleuren gebruikt worden, zolang maar aan deze voorwaarde voldaan is. Dat de functie $\chi (G,\lambda )$ inderdaad een veelterm is voor elke graaf kan inductief bewezen worden.

Voorbeelden

In deze driehoek kan de bovenste knoop in elk van de λ kleuren gekleurd worden. De linkerknoop kan dan nog in (λ-1) kleuren gekleurd worden en de rechterknoop in (λ-2) kleuren. De chromatische veelterm van deze complete graaf is dus λ(λ-1)(λ-2).

Voor een graaf die bestaat uit $n$ geïsoleerde knopen zonder kanten, kan elke knoop onafhankelijk van de andere een van de $\lambda$ kleuren krijgen. Het totale aantal kleuringen is dus $\chi (G,\lambda )=\lambda ^{n}$.

In een volledige graaf met $n$ knopen kan men een eerste knoop een van de $\lambda$ kleuren geven. Een volgende knoop is steeds verbonden met deze eerste knoop en kan dus nog $\lambda -1$ kleuren krijgen; een volgende $\lambda -2$ enz. De chromatische veelterm van een volledige graaf is dus:

$\chi (K_{n},\lambda )=\prod _{i=0}^{n-1}(\lambda -i)=\lambda (\lambda -1)\cdots (\lambda -n+1)$

Eigenschappen

Stel a en b zijn twee knopen in een graaf $G$ die geen buren zijn, d.w.z. ze zijn niet door een boog verbonden. Dan zijn de kleuringen van G in onder te verdelen in twee types:

• Type 1: die waarbij a en b verschillende kleuren hebben;
• Type 2: die waarbij a en b dezelfde kleur hebben.

Type 1 is een kleuring van de graaf $G'$ die men bekomt door in $G$ de kant (a,b) toe te voegen. De toevoeging van die kant schendt de vereiste van een geldige kleuring niet.

Type 2 komt overeen met de kleuring van een graaf $G''$ waarin knopen a en b samengevoegd zijn tot één knoop.

Er geldt nu: $\chi (G,\lambda )=\chi (G',\lambda )+\chi (G'',\lambda ).$

De chromatische veelterm van een graaf kan dus uitgedrukt worden in termen van de chromatische veeltermen van een graaf met een extra kant, en een andere graaf met een knoop minder. Dat kan recursief gebeuren tot men uitkomt op grafen die geen niet-naburige knopen hebben. Men verkrijgt dan de chromatische polynoom van de gegeven graaf als de som van de chromatische polynomen van complete grafen, die zoals hierboven is aangegeven veelterm zijn. Daaruit volgt dat de functie $\chi (G,\lambda )$ inderdaad voor elke graaf $G$ een veelterm is.

Deze drie grafen hebben dezelfde chromatische veelterm λ(λ-2)(λ-1)³

Als de graaf $G$ bestaat uit disjuncte componenten $G_{1},...G_{k}$, dan is $\chi (G,\lambda )=\chi (G_{1},\lambda )\cdot \chi (G_{2},\lambda )\cdots \chi (G_{k},\lambda ).$ De kleuring van elke component is volledig onafhankelijk van die van de andere en het totale aantal mogelijke kleuringen is dus gewoon het product van de aantallen kleuringen van de afzonderlijke componenten.

De chromatische veelterm van een boom met n knopen is $\lambda (\lambda -1)^{n-1}.$ Men kan de boom opbouwen beginnend met een graaf bestaande uit twee knopen en een kant daartussen. De chromatische veelterm hiervan is $\lambda (\lambda -1)$. Vervolgens voegt men een voor een de andere knopen toe, waarbij elke nieuwe knoop verbonden wordt met een knoop in de reeds gevormde deelboom. De nieuwe knoop kan $\lambda -1$ kleuren krijgen (enkel de kleur van de knoop waarmee hij verbonden is, is verboden). De toevoeging van een knoop vermenigvuldigt de chromatische veelterm dus met $\lambda -1$.

Isomorfe grafen hebben dezelfde chromatische veelterm; maar ook grafen die niet isomorf zijn kunnen eenzelfde chromatische veelterm hebben. Grafen met dezelfde chromatische veeltermen noemt men chromatisch equivalente grafen.

Toepassingen

• De vierkleurenstelling, die stelt dat elke planaire graaf kan gekleurd worden met vier kleuren, kan uitgedrukt worden als:

$\chi (G,4)\neq 0$ als $G$ planair is.

De Amerikaanse wiskundige George David Birkhoff voerde in 1912 de chromatische veelterm in als hulpmiddel voor dit probleem; het is het aantal manieren om een landkaart (die kan voorgesteld worden als een planaire graaf) te kleuren.

• Chromatische veeltermen kunnen in bepaalde problemen van operationeel onderzoek toegepast worden, bijvoorbeeld bij de toewijzing van kanalen aan televisiestations: stel er zijn n televisiestations die willen uitzenden in een zeker land, en er zijn k beschikbare zendfrequenties (kanaal). Twee nabije stations kunnen niet op hetzelfde kanaal uitzenden zonder storingen te veroorzaken. De kanalen moeten dan toegewezen worden zodat die situatie niet kan optreden. Hiervoor kan men een graaf opstellen met als knopen de stations. Twee stations die niet op hetzelfde kanaal mogen uitzenden worden met een kant verbonden. Een geldige toewijzing komt dan overeen met een geldige kleuring van de graaf in k kleuren. Het aantal mogelijke toewijzingen wordt gegeven door de chromatische veelterm van deze graaf.

Problemen

Een van de onopgeloste problemen in verband met chromatische veeltermen is of men van een willekeurige gegeven veelterm kan besluiten dat die de chromatische veelterm is van een of andere graaf. Er zijn een aantal noodzakelijke voorwaarden bekend (bijvoorbeeld: de termen in de veelterm moeten afwisselend positief en negatief zijn), maar geen sluitende noodzakelijke en voldoende voorwaarden. Een andere onopgeloste vraag is: wat zijn de noodzakelijke en voldoende voorwaarden opdat twee grafen dezelfde chromatische veeltermen hebben?

Bronnen, noten en/of referenties