Domneva 1-2-3 : magistrsko delo

Romih, Gašper Domen (avtor), Bašić, Nino (mentor)

Povezavna utežitev $\omega : E \rightarrow \{1,2, \ldots, k\}$ grafa $G = (V, E)$ določa barvanje grafa, kjer barvo vozlišča dobimo kot vsoto uteži na incidenčnih povezavah. Najmanjši tak $k$, za katerega obstaja utežitev, ki porodi pravilno barvanje, označimo z $\chi_\Sigma^e(G)$. To ni mogoče, če graf vsebuje izolirano povezavo. Zato obravnavamo samo grafe brez izoliranih povezav. V nalogi se osredotočimo na iskanje konstantne zgornje meje za parameter $\chi_\Sigma^e(G)$. Domneva 1-2-3 pravi, da velja $\chi_\Sigma^e(G) \le 3$ za vsak graf $G$. Domnevo potrdimo v primeru poti, ciklov, dvodelnih grafov, $3$-obarvljivih grafov in polnih grafov. Poleg tega predstavimo t.i.\ izrek 1-2-3-4-5, ki pravi, da velja $\chi_\Sigma^e(G) \le 5$ za vsak graf $G$. To je tudi najboljši rezultat do sedaj. V primeru regularnih grafov je mogoče rezultat malenkost izboljšati in pokazati, da velja $\chi_\Sigma^e(G) \le 4$ za vsak regularen graf $G$. Obravnavamo tudi asimptotsko obnašanje parametra na naključnih grafih. Poleg tega obravnavamo tudi totalno in seznamsko posplošitev problema. Razvijemo in analiziramo algoritem, ki za podan graf poišče utežitev za $k=3$, če taka utežitev obstaja.

• Jezik: Slovenski jezik
• Ključne besede: teorija grafov, kombinatorika, grafovski polinomi, naključni grafi, seznmsko barvanje, permanenta, kombinatorični izrek o ničlah
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2021
• PID: 20.500.12556/RUL-130553
• COBISS.SI-ID: 76518915
• Datum objave v RUL: 16.09.2021

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: 1-2-3 Conjecture

Izvleček

An edge weighting $\omega : E \rightarrow \{1,2, \ldots, k\}$ of a graf $G=(V,E)$ induces a vertex colouring where vertex colour is defined as a sum of weights on incident edges. The smallest $k$ for which there exists an edge weighting which induces a proper colouring is denoted by $\chi_\Sigma^e(G)$. If a graph contains an isolated edge then such a weighting does not exist. Therefore, we only consider graphs without isolated edges. We focus on providing constant upper bounds for parameter $\chi_\Sigma^e(G)$. The 1-2-3 conjecture states that $\chi_\Sigma^e(G) \le 3$ for any graph $G$. The conjecture is confirmed in a case of paths, cycles, bipartite graphs, $3$-colourable graphs and complete graphs. We present the so called 1-2-3-4-5 theorem which states that $\chi_\Sigma^e(G) \le 5$ for any graph $G$. In the case of regular graphs, the result can be improved. It can be show that $\chi_\Sigma^e(G) \le 4$ for any regular graphs. We also analyse asymptotic behaviour of the parameter on random graphs. Results for the total and list version of the problem are also presented. We developed and analysed an algorithm which for a given graph $G$ constructs an edge weighting for $k=3$ if such a weighting exists.

• Ključne besede: graph theory, combinatorics, graph polynomials, random graphs, list colouring, permanent, combinatorial nullstellensatz