Skoči na glavni sadržaj

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


Puni tekst: engleski pdf 200 Kb

str. 391-398

preuzimanja: 629

citiraj


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

https://hrcak.srce.hr/44031

Datum izdavanja:

9.12.2009.

Posjeta: 1.359 *