Star coloring of Hypercubes
Author
Grønhøj, Anette Hyllested
Term
4. term
Publication year
2010
Submitted on
2010-01-31
Pages
48
Abstract
Denne kandidatafhandling, afsluttet i efteråret 2019 på Institut for Matematiske Fag, Aalborg Universitet, undersøger stjernefarvning af hyperkuber. En hyperkube er en n-dimensionel version af en kube, og den stjerne-kromatiske tal angiver, hvor mange farver der mindst skal til for at farve hjørnerne, så farvningen både er korrekt (tilstødende hjørner har forskellige farver) og undgår visse små tofarvede mønstre. I 2004 gav Fertin, Raspaud og Reed lineære øvre og nedre grænser for hyperkubens stjerne-kromatiske tal, men afstanden mellem disse grænser vokser med dimensionen. Eksempler på stjernefarvninger af hyperkuber tyder dog på, at den publicerede nedre grænse ikke holder. Afhandlingen undersøger denne uoverensstemmelse. Da de oprindelige grænser bygger på en kobling mellem stjernefarvning og acyklisk farvning, udvikles der kriterier, som tydeligere adskiller de to begreber, med målet at gøre grænserne skarpere. Som led heri introduceres begrebet stjernekomponenter, og det vises, at de med passende kriterier kan bruges til at påvise, at den eksisterende nedre grænse for hyperkuber er for lav, hvilket peger mod mere præcise og tættere grænser.
This Master’s thesis, completed in autumn 2019 at the Department of Mathematical Sciences, Aalborg University, studies star coloring of hypercubes. A hypercube is an n-dimensional version of a cube; the star chromatic number is the minimum number of colors needed to color its vertices so the coloring is proper (adjacent vertices have different colors) and avoids certain small two-color patterns. In 2004, Fertin, Raspaud and Reed gave linear upper and lower bounds for this number, but the gap between them grows with dimension. Examples of star colorings of hypercubes suggest that the published lower bound does not hold. The thesis investigates this discrepancy. Because those bounds rely on linking star coloring to acyclic coloring, the work develops criteria that more clearly separate the two notions, aiming to tighten the bounds. To this end, it introduces the idea of star components and shows that, under suitable criteria, these can demonstrate that the existing lower bound for hypercubes is too low, pointing toward improved, closer bounds.
[This abstract was generated with the help of AI]
Keywords
Documents