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.