| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:b-barvanja regularnih grafov in grafovskih produktov
Authors:ID Premzl, Mojca (Author)
ID Jakovac, Marko (Mentor) More about this mentor... New window
Files:.pdf MAG_Premzl_Mojca_2016.pdf (1,97 MB)
MD5: 34AD4B70B4C52FD55F74C31B1063AA1E
 
Language:Slovenian
Work type:Master's thesis
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract: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.
Keywords:b-barvanje, b-kromatično število, NP-poln problem, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt, direktni produkt.
Place of publishing:Maribor
Publisher:[M. Premzl]
Year of publishing:2016
PID:20.500.12556/DKUM-62028 New window
UDC:519.174(043.2)
COBISS.SI-ID:22663432 New window
NUK URN:URN:SI:UM:DK:ZNSXVBZJ
Publication date in DKUM:14.10.2016
Views:1665
Downloads:122
Metadata:XML DC-XML DC-RDF
Categories:FNM
:
Copy citation
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share



Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:English
Title:b-colorings of regular graphs and graph products
Abstract:A b-coloring of a graph $G$ is a proper coloring of its vertices such that every color class contains a vertex that has a neighbor in all other color classes. The b-chromatic number of a graph $G$, denoted by $varphi(G)$, is the largest integer $k$ such that the graph has a b-coloring with $k$ colors. In this thesis we introduce the definition of b-coloring and we give some exact values of the b-chromatic number of paths, cycles, complete graphs, stable graphs and complete bipartite graphs. We prove that determining the b-chromatic number for an arbitrary graph is NP-complete and that is why we can determine the b-chromatic number just for few family of graphs. From the definition of the b-coloring it is clear that $chi(G) leq varphi(G) leq Delta(G)+1$. We give some other upper bounds for the b-chromatic number of arbitrary graphs. One of them is the $m$-degree of a graph $G$, $m(G)$; this is the largest integer $m$ such that $G$ has at least $m$ vertices with degree at least $m-1$. The b-chromatic number can be exactly determined for trees in polynomial time. In chapter three we consider conditions, that must be fulfilled in a $d$-regular graph, that its b-chromatic number equals the upper bound, that is $d+1$. One of the conditions is that the graph has at least $2d^3$ vertices. We show that, if $G$ is $d$-regular with $g(G) geq 6$ or if $g(G) geq 5$ and the graph either contains no $6$-cycles or $dleq 6$, then $varphi(G)=d+1$. Some $d$-regular grphs have small b-chromatic number even if $d$ is a large number (e.g. bipartite graph $K_{d,d}$) . We show that for a $d$-regular graph with no $4$-cycles the b-chromatic number grows linearly with the value of $d$. Every $d$-regular graph with no $4$-cycles and $textrm{diam}(G)geq 6$ has b-chromatic number $d+1$. This also holds for every regular graph with no $4$-cycle and $kappa(G)leq frac{d+1}{2}$, where $kappa(G)$ denotes the vertex connectivity. At the end of this chapter we show that there are exactly four cubic graphs with $varphi(G) leq d$, one of them being the Petersen graph. In the last chapter we discuss b-colorings of graph products: the Cartesian, the strong, the lexicographic and the direct product. In the case of the Cartesian and the direct product a lower bound for the b-chromatic number is $max left{varphi(G), varphi(H)right}$, in the case of the strong and the lexicographic product a lower bound equals to $varphi(G) cdot varphi(H)$. For each product we also give an upper bound for the b-chromatic number. We give some exact values for the b-chromatic number of graph products where factors are paths, cycles, stars, and in some cases one of the factors can be an arbitrary graph.
Keywords:b-coloring, b-chromatic number, NP-complete problem, regular graph, Cartesian product, strong product, lexicographic product, direct product.


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica