Jezik: | Angleški jezik |
---|---|
Leto izida: | 2009 |
Tipologija: | 1.01 - Izvirni znanstveni članek |
Organizacija: | UL FS - Fakulteta za strojništvo |
UDK: | 519.17 |
COBISS: | 15524441 |
ISSN: | 1331-0623 |
Št. ogledov: | 32 |
Št. prenosov: | 11 |
Ocena: | 0 (0 glasov) |
Metapodatki: |
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 |