Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph

Petra Šparl (Author), Janez Žerovnik (Author)

Abstract

Problem odločanja ali obstaja homomorfizem iz poljubnega grafa ▫$G$▫ v dani graf ▫$H$▫ je bil že večkrat proučevan in se je izkazal za zelo težkega. Hell in Nešetril sta dokazala, da je odločitveni problem NP-poln, če ▫$H$▫ ni dvodelen graf. V članku je obravnavan poseben problem, kjer je ▫$G$▫ poljuben heksagonalen graf brez trikotnikov, ▫$H$▫ pa Kneserjev graf ali njegov inducirani podgraf. Podana je esplicitna konstrukcija, ki dokazuje obstoj homomorfizma iz poljubnega heksagonalnega grafa brez trikotnikov v Petersenov graf brez ene točke.

Keywords

matematika;teorija grafov;homomorfizem;H-barvanje;heksagonalen graf brez trikotnikov;mathematics;homomorphism;H-coloring;triangle-free hexagonal graph;

Data

Language:	English
Year of publishing:	2009
Typology:	1.01 - Original Scientific Article
Organization:	UL FS - Faculty of Mechanical Engineering
UDC:	519.17
COBISS:	15524441
ISSN:	1331-0623
Views:	32
Downloads:	11
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Ekspliciten homomorfizem heksagonalnih grafov v Petersenov graf brez ene točke
Secondary abstract:	The problem of deciding whether an arbitrary graph ▫$G$▫ has a homomorphism into agiven graph ▫$H$▫ has been widely studied and has turned out to be very difficult. Hell and Nešetril proved that the decision problem is NP-complete unless ▫$H$▫ is bipartite. We consider a restricted problem where ▫$G$▫ is an arbitrary triangle-free hexagonal graph and ▫$H$▫ is a Kneser graph or its induced subgraph. We give an explicit construction which proves that any triangle-free hexagonal graph has a homomorphism into one-vertex deleted Petersen graph.
Secondary keywords:	matematika;teorija grafov;homomorfizem;H-barvanje;heksagonalen graf brez trikotnikov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 391-398
Volume:	ǂVol. ǂ14
Issue:	ǂno. ǂ2
Chronology:	2009
ID:	1475030