E-viri
Recenzirano
Odprti dostop
-
Brewster, Richard C.; Lee, Jae‐Baek; Moore, Benjamin; Noel, Jonathan A.; Siggers, Mark
Journal of graph theory, July 2020, 2020-07-00, 20200701, Letnik: 94, Številka: 3Journal Article
For a fixed graph H, the reconfiguration problem for H‐colorings (ie, homomorphisms to H) asks: given a graph G and two H‐colorings φ and ψ of G, does there exist a sequence f0,…,fm of H‐colorings such that f0=φ, fm=ψ, and fi(u)fi+1(v)∈E(H) for every 0≤i<m and uv∈E(G)? If the graph G is loop‐free, then this is the equivalent to asking whether it possible to transform φ into ψ by changing the color of one vertex at a time such that all intermediate mappings are H‐colorings. In the affirmative, we say that φ reconfigures to ψ. Currently, the complexity of deciding whether an H‐coloring φ reconfigures to an H‐coloring ψ is only known when H is a clique, a circular clique, a C4‐free graph, or in a few other cases which are easily derived from these. We show that this problem is PSPACE‐complete when H is an odd wheel. An important notion in the study of reconfiguration problems for H‐colorings is that of a frozen H‐coloring; that is, an H‐coloring φ such that φ does not reconfigure to any H‐coloring ψ such that ψ≠φ. We obtain an explicit dichotomy theorem for the problem of deciding whether a given graph G admits a frozen H‐coloring. The hardness proof involves a reduction from a constraint satisfaction problem which is shown to be nondeterministic polynomial time NP‐complete by establishing the nonexistence of a certain type of polymorphism.
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|
Vir: Osebne bibliografije
in: SICRIS
To gradivo vam je dostopno v celotnem besedilu. Če kljub temu želite naročiti gradivo, kliknite gumb Nadaljuj.