Loading AI tools
Från Wikipedia, den fria encyklopedin
Det kromatiska polynomet för en graf är ett begrepp inom matematiken, speciellt grafteorin. Låt vara en graf. Då är det kromatiska polynomet det polynom som anger på hur många sätt kan färgläggas med 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.
Graden av är lika med antalet noder i . Även icke-isomorfa grafer kan ha samma kromatiska polynom.
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 består av flera sammanhängande komponenter är lika med produkten av de kromatiska polynomen för varje komponent.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.