Petra Šparl (Avtor), Janez Žerovnik (Avtor)

Povzetek

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.

Ključne besede

matematika;teorija grafov;homomorfizem;H-barvanje;heksagonalen graf brez trikotnikov;mathematics;homomorphism;H-coloring;triangle-free hexagonal graph;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 15524441 Povezava se bo odprla v novem oknu
ISSN: 1331-0623
Št. ogledov: 32
Št. prenosov: 11
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni naslov: Ekspliciten homomorfizem heksagonalnih grafov v Petersenov graf brez ene točke
Sekundarni povzetek: 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.
Sekundarne ključne besede: matematika;teorija grafov;homomorfizem;H-barvanje;heksagonalen graf brez trikotnikov;
URN: URN:SI:UM:
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 391-398
Letnik: ǂVol. ǂ14
Zvezek: ǂno. ǂ2
Čas izdaje: 2009
ID: 1475030