Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graphŠparl, Petra (Avtor) Žerovnik, Janez (Avtor) matematikateorija grafovhomomorfizemH-barvanjeheksagonalen graf brez trikotnikovmathematicsteorija grafovhomomorphismH-coloringtriangle-free hexagonal graphProblem 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.20092015-07-10 15:15:43Delo ni kategorizirano51856UDK: 519.17OceCobissID: 8266073COBISS_ID: 15524441ISSN pri članku: 1331-0623NUK URN: URN:SI:UM:DK:WOPETDQHsl