Anti-Ramseyeva številaZmazek, Eva (Avtor) Klavžar, Sandi (Mentor) barvanje povezavmavricaanti-Ramseyevo številohiperkockaBarvanje povezav $c$ grafa $G$ je mavrica, če poljubni različni povezavi grafa $G$ pri barvanju $c$ prejmeta različni barvi. Anti-Ramsejevo število $\text{ar}(G,H)$ urejenega para enostavnih grafov $G$ in $H$ je najmanjše naravno število $r$, pri katerem za vsako $r$-barvanje povezav $c$ grafa $G$ z natanko $r$ barvami obstaja $H$-podgraf, za katerega je zožitev $c|H$ mavrica. Za nekatere pare grafov znamo določiti točne vrednosti anti-Ramseyevih števil. Pokažemo na primer lahko, da je anti-Ramseyevo število $\text{ar}(K_n,P_4)$ na paru grafov $K_n$ in $P_4$ enako $4$, če je $n=4$, in je enako $2$, če je $n \geq 5$. Kljub temu, da imata grafa $P_4$ in $C_3$ enako število povezav, se anti-Ramseyevi števili $\text{ar}(K_n,P_4)$ in $\text{ar}(K_n,C_3)$ zelo razlikujeta. Anti-Ramseyevo število $\text{ar}(K_n,C_3)$ je namreč enako številu $n$ vozlišč grafa $K_n$. Anti-Ramseyevo število znamo natančno določiti tudi na paru hiperkock $Q_n$ in $Q_{n-1}$. To je pri $n=3,4,5$ le za $3$, pri $n \geq 6$ pa le za $2$ manjše od števila povezav grafa $Q_n$.20202020-03-05 08:15:02Magistrsko delo/naloga114687sl