Kromatiskt polynom

Det kromatiska polynomet för en graf är ett begrepp inom matematiken, speciellt grafteorin. Låt $G$ vara en graf. Då är det kromatiska polynomet $P_{G}(k)$ det polynom som anger på hur många sätt $G$ kan färgläggas med $k$ färger.

Att det finns en sådan funktion för varje graf är uppenbart men att det faktiskt är ett polynom för varje given graf är inte lika självklart men ändå sant.

Egenskaper

Graden av $P_{G}(k)$ är lika med antalet noder i $G$. Även icke-isomorfa grafer kan ha samma kromatiska polynom.

• Alla koefficienterna i ett kromatiskt polynom är heltal.
• Den ledande koefficienten är alltid 1.
• Koefficienterna alternerar i tecken
• Den konstanta termen är noll
• Antingen är $P_{G}(x)=x^{n}$ eller så är summan av koefficienterna 0.

Dessa egenskaper räcker inte för att karakterisera kromatiska polynom, eller med andra ord, det finns polynom med alla dessa egenskaper och som inte är kromatiska polynom till någon graf. Att hitta egenskaper som karakteriserar kromatiska polynom är en öppen fråga.

Om $G$ består av flera sammanhängande komponenter är $P_{G}(k)$ lika med produkten av de kromatiska polynomen för varje komponent.

Historia

Kromatiska polynom definierades av George David Birkhoff 1912 för plana grafer som en del av ett försök att bevisa fyrfärgssatsen. Hassler Whitney generaliserade definitionen till godtyckliga grafer år 1932.