Pakirno barvanje grafaLičina, Tomaž (Avtor) Dravec, Tanja (Mentor) barvanje grafovpakirno barvanje grafovdrevesagrafi Mycielskegakartezični produkt grafovklično številoneodvisnostno številovozliščno pokritjePakirno barvanje grafe je dobro barvanje vozlišč, pri katerem sta poljubni dve vozlišči z isto barvo i na razdalji večji kot i. Pakirno kromatično število je najmanjše število barv, ki jih potrebujemo za tako barvanje grafa. V magistrskem delu obravnavamo pakirno kromatično število nekaterih družin grafov in zvezo pakirnega kromatičnega števila z drugimi grafovskimi invariantami. Podrobneje obravnavamo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. V prvem delu proučujemo pakirno kromatično število na osnovnih družinah grafov, na drevesih, kartezičnih produktih grafov in na grafih Mycielskega. V naslednjem delu obravnavamo grafe z majhnimi pakirnimi kromatičnimi števili in pokažemo, da je preveriti, ali ima graf pakirno kromatično število enako 4, NP-težek problem. V tretjem delu prikažemo zvezo pakirnega kromatičnega števila z neodvisnostnim številom grafa, najmanjšim vozliščnim pokritjem grafa in maksimalno stopnjo v grafu. V zadnjem delu raziskujemo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. Poiščemo trojice naravnih števil (a,b,c) za katere obstaja graf G s kličnim številom a, kromatičnim številom b in pakirnim kromatičnim številom c.[T. Ličina]20212021-11-09 12:01:43Magistrsko delo/naloga80891sl