Original scientific paper

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

Abstract

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.

Keywords

homomorphism; H-coloring; triangle-free hexagonal graph

Hrčak ID:

44031

URI

https://hrcak.srce.hr/44031

Publication date:

9.12.2009.

Visits: 1.359 *