b-barvanja regularnih grafov in grafovskih produktov : magistrsko delo
Harb, Mojca
Dobro barvanje vozlišč grafa $G$, v katerem v vsakem barvnem razredu obstaja vsaj eno tako vozlišče, ki ima vsaj enega soseda v vsakem drugem barvnem razredu, je b-barvanje grafa $G$. Največje ...naravno število $k$, za katerega graf premore b-barvanje s $k$ različnimi barvami, imenujemo b-kromatično število grafa in ga označimo s $varphi(G)$. V magistrskem delu bomo predstavili definicijo b-barvanja in podali natančne vrednosti b-kromatičnega števila za poti, cikle, polne grafe, neodvisne množice in polne dvodelne grafe. Dokazali bomo, da je določanje b-kromatičnega števila NP-poln problem, kar ima za posledico dejstvo, da lahko b-kromatično število natančno določimo le nekaterim družinam grafov. Že iz same definicije b-barvanja sledi, da je $chi(G) leq varphi(G) leq Delta(G)+1$. Podali bomo še nekaj zgornjih mej b-kromatičnega števila, ki veljajo za poljubne grafe. Med njimi izpostavimo predvsem $m$-stopnjo grafa $m(G)$; to je največje tako število $m$, za katerega graf $G$ vsebuje vsaj $m$ vozlišč stopnje vsaj $m-1$. Natančno vrednost b-kromatičnega števila lahko med drugim določimo tudi poljubnemu drevesu, in to v polinomskem času. V poglavju o regularnih grafih bomo obravnavali predvsem pogoje, ki jim mora zadoščati $d$-regularen graf, da bo njegovo b-kromatično število enako zgornji meji, to je $d+1$. Eden izmed pogojev je, da ima graf zadostno število vozlišč, in sicer vsaj $2d^3$. Dokazali bomo tudi, da je v $d$-regularnem grafu $varphi(G)=d+1$, če je ožina grafa $g(G) geq 6$ oz. če je $g(G)geq 5$ in graf bodisi ne vsebuje nobenega cikla dolžine $6$ bodisi je $d leq 6$. Nekateri $d$-regularni grafi lahko imajo kljub velikemu $d$ majhno b-kromatično število (npr. dvodelni graf $K_{d,d}$). Dokazali bomo, da velikost b-kromatičnega števila $d$-regularnih grafov, ki ne vsebujejo nobenega $4$-cikla, linearno narašča z velikostjo $d$. Za regularne grafe, ki ne vsebujejo nobenega $4$-cikla in imajo $mathrm{diam}(G) geq 6$, prav tako velja, da je $varphi(G)=d+1$. Enako velja tudi za vse regularne grafe, ki ne vsebujejo nobenega $4$-cikla, njihova vozliščna povezanost pa je $kappa(G) leq frac{d+1}{2}$. Nazadnje bomo dokazali še, da obstajajo le štirje kubični grafi, za katere je $varphi(G) leq d$, eden izmed njih je Petersenov graf. V zadnjem poglavju bomo obravnavali b-barvanja grafovskih produktov, in sicer kartezičnega, krepkega, leksikografskega in direktnega. V primeru kartezičnega in direktnega produkta je b-kromatično število navzdol omejeno z $max left{varphi(G), varphi(H) right}$, v primeru krepkega in leksikografskega produkta pa je spodnja meja enaka $varphi(G) cdot varphi(H)$. Za vsak produkt posebej bomo podali še zgornjo mejo b-kromatičnega števila. Določili bomo še nekatere natančne vrednosti b-kromatičnega števila grafovskih produktov, pri čemer bodo posamezni faktorji enaki potem, ciklom, zvezdam, v nekaterih primerih pa bo eden izmed faktorjev celo poljuben graf.
Type of material - master's thesis
; adult, serious
Publication and manufacture - Maribor : [M. Premzl], 2016
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
