Chromatische veelterm
De chromatische veelterm  van een graaf  geeft het aantal mogelijke geldige knopenkleuringen met  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  kleuren gebruikt worden, zolang maar aan deze voorwaarde voldaan is. Dat de functie  inderdaad een veelterm is voor elke graaf kan inductief bewezen worden.

Voorbeelden

Voor een graaf die bestaat uit  geïsoleerde knopen zonder kanten, kan elke knoop onafhankelijk van de andere een van de  kleuren krijgen. Het totale aantal kleuringen is dus .

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

Eigenschappen
Stel a en b zijn twee knopen in een graaf   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  die men bekomt door in  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  waarin knopen a en b samengevoegd zijn tot één knoop. 

Er geldt nu: 

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  inderdaad voor elke graaf  een veelterm is.

Als de graaf  bestaat uit disjuncte componenten , dan is  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  Men kan de boom opbouwen beginnend met een graaf bestaande uit twee knopen en een kant daartussen. De chromatische veelterm hiervan is . 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  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 .

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:
 als  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?

Grafentheorie
Veelterm