| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph
Authors:Šparl, Petra (Author)
Žerovnik, Janez (Author)
Files:URL http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=68552
Work type:Not categorized (r6)
Typology:1.01 - Original Scientific Article
Organization:FOV - Faculty of Organizational Sciences in Kranj
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, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph
Year of publishing:2009
Number of pages:str. 391-398
Numbering:Vol. 14, no. 2
ISSN on article:1331-0623
COBISS_ID:15524441 New window
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Mathematical communications
Shortened title:Math. commun., Croat. Math. Soc., Divis. Osijek
Publisher:Croatian Mathematical Society - Division Osijek
COBISS.SI-ID:8266073 New window

Secondary language

Title:Ekspliciten homomorfizem heksagonalnih grafov v Petersenov graf brez ene točke
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.


Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
There are no comments!

Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica