Publikace na Matematicko-fyzikální fakulta |
2010
Abstrakt
Zkoumáme grafy, které je možno reprezentovat jako sousednostní grafy souvislých podgrafů nekonečné diagonálně rozšířené čtvercové sítě. Tento pojem dává do souvislosti string grafy na straně jedné (neomezené velikosti podgrafů) a indukované podgrafy rozšířené sítě (jednovrcholové podgrafy).
Vyslovujeme hypotézu, že pro každé k je NP-úplné rozpoznat grafy reprezentovatelné podgrafy velikosti nejvýše k. Tuto hypotézu dokazujeme pro všechna k5.