aalto1 untyped-item.component.html
Roots of chromatic polynomials
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Bachelor's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
SCI3029
Degree programme
Language
en
Pages
19
Series
Abstract
Graph coloring means giving some value for each node in a graph such that adjacent nodes have different values. The values can be anything but often they are referred to as colors and the process as graph coloring. Graph coloring began with the problem of coloring regions in a map such that neighboring regions would have different colors.
An interesting question in graph coloring is in how many different ways a specific graph can be colored using a certain number of colors. For every graph we can determine a chromatic polynomial. The chromatic polynomial is a polynomial function where the input is the number of available colors and the output tells in how many ways the graph can be colored using at most that number of colors.
In this work we looked at some basic properties of chromatic polynomials, specifically concerning their roots. We also studied chordal graphs and their chromatic polynomials and roots in more detail.
For results we found that all positive integers are a root of some chromatic polynomial, no negative integers are a root of any chromatic polynomial and no chromatic polynomial has roots in the intervals (0,1) and (1,32/27]. For chordal graphs we found a formula for their chromatic polynomials and found that they only have nonnegative integer roots.
Graafin värityksessä graafin solmuille annetaan jotkin arvot siten, että viereisillä solmuilla on eri arvot toisistaan. Arvot voivat olla mitä tahansa mutta usein niistä puhutaan väreinä ja prosessista täten värityksenä. Graafien väritys lähti liikeelle alueiden värittämisestä kartassa, missä naapurimaat haluttiin värittää eri väreillä.
Graafien värityksessä kiinnostava kysymys on kuinka monella eri tavalla tietty graafi voidaan värittää, jos käytössä on tietty määrä värejä. Jokaiselle graafille voidaan määrittää kromaattinen polynomi. Kromaattiinen polynomi on polynomifunktio, jossa muuttujana on käytettävien värien määrä ja joka kuvaa kuinka monella eri tavalla graafi voidaan värittää käyttämällä enintään tätä määrää värejä.
Kaikille kromaattisille polynomeille voidaan määrittää joitain yhteisiä ominaisuuksia. Tässä työssä tutustuttiin tutkimuskirjallisuuteen kromaattisista polynomeista ja tutkittiin joitain niiden ominaisuuksia, erityisesti niiden juuria eli nollakohtia. Työssä tutustuttiin myös tarkemmin jänteellisiin graafeihin (engl. chordal graph) ja tutkittiin näiden kromaattisia polynomeja ja niiden juuria.
Tuloksiksi kromaattisten polynomien juurille havaittiin että kaikki positiiviset kokonaisluvut ovat jonkin kromaattisen polynomin juuria, mikään negatiivinen reaaliluku ei ole minkään kromaattisen polynomin juuri ja millään kromaattisella polynomilla ei ole juuria väleissä (0,1) tai (1,32/27]. Jänteellisille graafeille johdettiin kaava niiden kromaattisille polynomeille ja löydettiin että näiden polynomien juuret ovat vain ei-negatiivisia kokonaislukuja. Muilla kromaattisilla polynomeilla voi olla myös komplekseja juuria.