Referaatopsomming

’n Fynbedagte kleurespel in grafiekteorie

E.C.M. Maritz, S. Dorfling, T. Vetrik

Copyright: © 2016. The Author(s). Licensee: AOSIS.
This is an Open Access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A clever colouring game in graph theory. In this study we focus on a generalised colouring of graphs, namely a metric chromatic colouring. We determine new upper bounds for the metric chromatic number of wheels and circulant graphs and show that these boundaries are an improvement on existing values.

Die veralgemeende kleuring van grafieke het in die laaste jare ontsaglik uitgebrei danksy toepassings in, onder meer, die rekenaarwetenskappe en biologiese netwerke. Een van hierdie kleurings wat ons bestudeer, is die metriese chromatiese getal (MCG) van ’n grafiek. Hierdie konsep vorm ’n verband tussen die bekende metriese dimensie van ’n grafiek en dié van veralgemeende kleurings.

In die literatuur bestaan daar tans algemene resultate en grense vir hierdie parameter, maar daar is ’n gaping wanneer dit kom by spesifieke grafiekklasse. Daar is bewys dat die bestaande grense skerp is, maar daar bestaan tog grafieke waarvoor die waardes beduidend kan verskil.

Die metriese chromatiese getalle van grafieke, soos paaie en siklusse, is reeds bepaal; dus oorweeg ons in hierdie studie die grafiekklasse van wiele en sirkulantgrafieke wat albei uitbreidings van die bogenoemde grafieke is, as volgende stap.

Die metriese chromatiese getal word gedefinieer as die kleinste positiewe heelgetal (die minste getal kleure) waarmee ons ’n grafiek op ’n sekere wyse kan inkleur. Volgens die kleuring van die grafiek ken ons vir elk van die punte ’n kode toe wat streng gesproke bestaan uit afstande na die naaste punte van die afsonderlike kleure wat gebruik is. Ons vereis dat alle pare van twee aangrensende punte unieke kodes moet hê. Dus is ons benadering om te mik vir ’n bogrens wat na aan ons verwagting van die MCG is, en te wys dat daar vir alle grootte grafieke so ’n kleuring bestaan.

Ons maak gebruik van die inherente sikliese eienskap van sirkulantgrafieke om ’n patroon te vind waarmee ons die afstande in die grafiek kan bepaal. Afhangend van die getal punte in die grafiek, kan ons dan ’n kleuring toeken en die afstande gebruik om te bewys dat elke paar aangrensende punte unieke kodes het.

Hiermee verbeter ons huidige bogrense en toon terselfdertyd aan dat ons parameter verskil van die welbekende chromatiese getal, asook die partisiedimensie van ’n grafiek: ’n parameter wat slegs op ’n enkele punt in die definisie verskil van die MCG.