Star coloring of Hypercubes

Studenteropgave: Master afgangsprojekt

  • Anette Hyllested Grønhøj
4. semester, Master i Matematik (Efter- og videreuddannelse) (Masteruddannelse)
Dette speciale er skrevet ved Institutet for Matematiske Fag, Aalborg Universitet og behandler begreber indenfor punktfarvning af grafer. Stjernefarvning er en gren af punktfarvning, hvor to nabopunkter skal være farvet forskelligt og hvor en grafisk vej af længde 3 aldrig må blive to-farvet. Som for enhver punktfarvning opstår et optimeringsproblem: Hvad er det mindste mulige antal farver, der findes nødvendig for at kunne punktfarve grafen korrekt? For stjernefarvning kaldes dette det stjerne-kromatiske tal $\chi_s(G)$ for en graf $G$.

Grafen der behandles i dette speciale er de såkaldte Hypercubes $Q_n$. Disse grafer er konstrueret ved et kartetisk produkt, hvilket giver for dimension $n$ en $n$-regulær graf med $2^n$ punkter og $n2^{n-1}$ kanter.\\
I 2004, Guillaume Fertin, André Raspaud og Bruce Reed sammen deres bevis for øvre og nedre grænser for the stjernekromatiske tal $\chi_s(Q_n)$.

Hovedvægten for dette speciale lægges på, at G. Fertin, A. Raspaud og B. Reed bygger deres resultater for stjernefarvning på acyklisk farvning og at det acykliske kromatiske tal er mindre end eller lig med det stjerne-kromatiske tal. Med andre ord, alle stjernefarvninger er acykliske, men langt fra alle acykliske farvninger er stjernefarvninger.\\
Begge grænser for det stjerne-kromatiske tal er linære funktioner afhængige af dimensionen $n$ og når denne vokser, vokser afstanden mellem funktionsværdierne også. Derfor er det af stor interesse i dette speciale, at undersøge og om muligt at indsnævre denne afstand.\\
Dertil undersøges først udførte stjernefarvninger af Hypercubes for at bestemme givne resultater for disse.\\
Dernæst undersøges de anvendte argumenter i beviserne for Guillaume Fertin, André Raspaud og Bruce Reeds resultater.
SprogEngelsk
Udgivelsesdato31 jan. 2010
Antal sider48
ID: 319282149