20.500.12556/DKUM-62028 b-barvanja regularnih grafov in grafovskih produktov b-colorings of regular graphs and graph products 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. 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. b-barvanje b-kromatično število NP-poln problem regularni graf kartezični produkt krepki produkt leksikografski produkt direktni produkt. b-coloring b-chromatic number NP-complete problem regular graph Cartesian product strong product lexicographic product direct product. true true false [M. Premzl] Slovenski jezik Angleški jezik Magistrsko delo 2016-08-22 00:37:01 2016-10-14 12:57:40 2022-06-28 03:07:28 2019-07-11 12:41:05 2016 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.174(043.2) 22663432 URN:SI:UM:DK:ZNSXVBZJ MAG_Premzl_Mojca_2016.pdf MAG_Premzl_Mojca_2016.pdf 1 34AD4B70B4C52FD55F74C31B1063AA1E 1de51fdec3cc22868eed67097be17a3a37b0b1273f663ecffdb039635e8078e9 8f5d8bd4-7c0d-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=105499 Fakulteta za naravoslovje in matematiko 0 0 0