Späť

Stenovo kompletné zafarbenie hrán rovinných grafov

Facial Complete Edge-Colouring of Plane Graphs

Mgr. Michaela Vrbjarová
Univerzita Pavla Jozefa Šafárika v Košiciach, Prírodovedecká fakulta
Ústav matematických vied
Jesenná 5, 040 01 Košice

Abstrakt:
Hranové zafarbenie súvislého rovinného grafu G sa nazýva stenovo kompletné zafarbenie hrán grafu G, ak ľubovoľné dve stenovo susedné hrany grafu sú zafarbené rôznymi farbami a zároveň, ak pre každú stenu f grafu G platí, že pre ľubovoľné dve farby použité v zafarbení hrán steny f existuje dvojica susedných hrán incidentných so stenou f, ktoré sú zafarbené týmito dvoma farbami. Maximálny počet farieb, ktorými sa dá zafarbiť rovinný graf G, aby toto zafarbenie bolo stenovo kompletné zafarbenie hrán grafu G, sa nazýva stenovo achromatický index grafu G. Nie pre každý súvislý rovinný graf existuje stenovo kompletné zafarbenie a teda, ak máme daný konkrétny rovinný graf G vyvstávajú dve otázky a to, či existuje vôbec jeho stenovo kompletné zafarbenie hrán a ak existuje, aký je jeho stenovo achromatický index. V príspevku sa zaoberáme určením stenovo achromatického indexu pre špeciálne triedy rovinných grafov.

Kľúčové slová:
rovinný graf, hranové zafarbenie, stenovo kompletné zafarbenie hrán, stenovo achromatický index, stena

Abstract:
An edge-colouring of a connected plane graph G is called a facial complete edge-colouring, if arbitrary two facial-adjacent edges are assigned different colours and moreover, for every face f of graph G and every two colours used on this face, there are two adjacent edges incident with the face f, that they are assigned this two colours. The maximum number that there exists a facial complete edge-colouring of a connected plane graph G, which uses this number of colours, is called a facial achromatic index of the graph G. Not every connected plane graph is facial complete edge-colourable, so we can ask two questions. First we can ask, whether given graph G is facial complete edge-colourable and if answer is yes, we can ask for facial achromatic index of this graph. In this paper we determine the facial achromatic index for some special classes of plane graphs.

Keywords:
plane graph, edge-colouring, facial complete edge-colouring, facial achromatic index, face

Späť