Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Petra Šparl, Janez Žerovnik · University of Maribor digital library (University of Maribor) · 2009
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.