Anti-Ramseyeva števila : magistrsko delo

Zmazek, Eva (author), Klavžar, Sandi (mentor)

Barvanje 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$.

• Language: Slovenian
• Keywords: barvanje povezav, mavrica, anti-Ramseyevo število, hiperkocka
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2020
• PID: 20.500.12556/RUL-114687
• UDC: 519.1
• COBISS.SI-ID: 18938457
• Publication date in RUL: 05.03.2020

ZMAZEK, Eva, 2020, Anti-Ramseyeva števila : magistrsko delo [online]. Master’s thesis. [Accessed 17 March 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=114687

Secondary language

• Language: English
• Title: Anti-Ramsey numbers

Abstract

An edge coloring $c: E(G) \to [k]$ of a graph $G$ is called a rainbow if all of its edges are colored with different colors. An Anti-Ramsey number $\text{ar}(G,H)$ for an ordered pair of graphs $G$ and $H$ is the smallest number $r$ such that for every edge coloring $c$ of $G$ with exactly $r$ colors, there exists an $H$-subgraph of $G$ such that the coloring $c$ on $H$ is a rainbow. We determine exact values of the anti-Ramsey numbers for some particular pairs of graphs. For example, we show that the exact value of the anti-Ramsey number $\text{ar}(K_n,P_4)$ for a pair of graphs $K_n$ and $P_4$ is equal to $4$ if $n=4$, and is equal to $2$ if $n \geq 5$. Even though the graphs $P_4$ and $C_3$ have the same number of edges, the anti-Ramsey numbers $\text{ar}(K_n,P_4)$ and $\text{ar}(K_n,C_3)$ differ significantly. This is because the anti-Ramsey number $\text{ar}(K_n,C_3)$ is equal to the number $n$ of vertices in $K_n$. We also determine the exact value of the anti-Ramsey number for a pair of hypercubes $Q_n$ and $Q_{n-1}$. It turns out that when $n=3,4$ or $5$, the anti-Ramsey number $\text{ar}(Q_n,Q_{n-1})$ is smaller than the number of edges in graph $Q_n$ by $3$, and in case when $n \geq 6$ it is smaller by $2$.

• Keywords: edge coloring, rainbow, anti-Ramsey number, hypercube