Star coloring of Hypercubes

Grønhøj, Anette Hyllested

4. term

Master of Mathmatics (Continuing education)

2010

2020-01-10

48 pages

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.

This Master of Science Thesis is written by Anette Hyllested Grønhøj in the autumn of 2019 during the last semester of a Master’s degree programme in Mathematics at the Department of Mathematical Sciences at Aalborg University. In 2004, G. Fertin, A. Raspaud and B. Reed published their proof of the bounds to the star chromatic number of Hypercubes $\chi_s(Q_n)$. These are two linear functions where the gap between them grows for every dimension $n$ in $Q_n$. In examples on star coloring of Hypercubes, it was noticed that the lower bound does not hold. For this Master's Thesis, this has been examined and since the bounds are based on the relation made between star coloring and acyclic coloring, this thesis has sought to establish possible criteria to separate them in order to draw the upper and lower bound to the star chromatic number for Hypercubes closer together. This has led to the introduction of the concept of star components and how these with the right criteria will proof that the lower bound is too low for a star coloring of a hypercube to be correct.

Hypercubes ; star coloring ; acyclic coloring ; star chromatic number ; star components

Download
View record in AAU Student Projects