b-barvanja regularnih grafov in grafovskih produktov

magistrsko delo

Mojca Harb (Author), Marko Jakovac (Mentor)

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

magistrska dela;b-barvanje;b-kromatično število;NP-poln problem;regularni grafi;kartezični produkti;krepki produkti;leksikografski produkti;direktni produkti;

Data

Language:	Slovenian
Year of publishing:	2016
Typology:	2.09 - Master's Thesis
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
Publisher:	[M. Premzl]
UDC:	519.174(043.2)
COBISS:	22663432
Views:	888
Downloads:	79
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	b-colorings of regular graphs and graph products
Secondary 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.
Secondary keywords:	master theses;b-coloring;b-chromatic number;NP-complete problem;regular graphs;Cartesian products;strong products;lexicographic products;direct products;
URN:	URN:SI:UM:
Type (COBISS):	Master's thesis
Thesis comment:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages:	XI f., 125 str.
ID:	9161504