Kromatiskt polynom

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

Kromatiska polynom definierades av George David Birkoff 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.