Izvorni znanstveni članak
Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Petra Šparl
; Faculty of Organizational Sciences, University of Maribor, Kranj, Slovenia
Janez Žerovnik
; Faculty of Mechanical Engineering, University of Ljubljana, Ljubljana, Slovenia
Sažetak
The problem of deciding whether an arbitrary graph G has a homomorphism into a given 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.
Ključne riječi
homomorphism; H-coloring; triangle-free hexagonal graph
Hrčak ID:
44031
URI
Datum izdavanja:
9.12.2009.
Posjeta: 1.032 *