| Naslov: | Explicit homomorphisms of hexagonal graphs to one vertex deleted Petersen graph |
|---|
| Avtorji: | ID Šparl, Petra (Avtor)
ID Žerovnik, Janez (Avtor) |
|---|
| Datoteke: |  http://hrcak.srce.hr/index.php?show=clanak&id_clanak_jezik=68552
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Delo ni kategorizirano |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FOV - Fakulteta za organizacijske vede
|
|---|
| Opis: | 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, teorija grafov, homomorphism, H-coloring, triangle-free hexagonal graph |
|---|
| Leto izida: | 2009 |
|---|
| Št. strani: | str. 391-398 |
|---|
| Številčenje: | Vol. 14, no. 2 |
|---|
| PID: | 20.500.12556/DKUM-51856  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 15524441 |
|---|
| ISSN pri članku: | 1331-0623 |
|---|
| NUK URN: | URN:SI:UM:DK:WOPETDQH |
|---|
| Datum objave v DKUM: | 10.07.2015 |
|---|
| Število ogledov: | 1453 |
|---|
| Število prenosov: | 34 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
