Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

List homomorphism problems for signed trees

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10453413" target="_blank" >RIV/00216208:11320/23:10453413 - isvavai.cz</a>

  • Výsledek na webu

    <a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=oRw9YxwlpE" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=oRw9YxwlpE</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.disc.2022.113257" target="_blank" >10.1016/j.disc.2022.113257</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    List homomorphism problems for signed trees

  • Popis výsledku v původním jazyce

    We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,σ), equipped with lists L(v),v in V(G), of allowed images, to a fixed target signed graph (H,π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v)=V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when H is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and in a future companion paper we will illustrate this by using them to classify the complexity for certain irreflexive signed graphs. The structure of the signed trees in the polynomial cases is interesting, suggesting that the class of general signed graphs for which the problems are polynomial may have nice structure, analogous to the so-called bi-arc graphs (which characterised the polynomial cases of list homomorphisms to unsigned graphs).

  • Název v anglickém jazyce

    List homomorphism problems for signed trees

  • Popis výsledku anglicky

    We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,σ), equipped with lists L(v),v in V(G), of allowed images, to a fixed target signed graph (H,π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v)=V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when H is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and in a future companion paper we will illustrate this by using them to classify the complexity for certain irreflexive signed graphs. The structure of the signed trees in the polynomial cases is interesting, suggesting that the class of general signed graphs for which the problems are polynomial may have nice structure, analogous to the so-called bi-arc graphs (which characterised the polynomial cases of list homomorphisms to unsigned graphs).

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • CEP obor

  • OECD FORD obor

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Návaznosti výsledku

  • Projekt

    <a href="/cs/project/GC19-17314J" target="_blank" >GC19-17314J: Geometrické reprezentace grafů</a><br>

  • Návaznosti

    P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Ostatní

  • Rok uplatnění

    2023

  • Kód důvěrnosti údajů

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Údaje specifické pro druh výsledku

  • Název periodika

    Discrete Mathematics

  • ISSN

    0012-365X

  • e-ISSN

  • Svazek periodika

    346

  • Číslo periodika v rámci svazku

    3

  • Stát vydavatele periodika

    NL - Nizozemsko

  • Počet stran výsledku

    24

  • Strana od-do

    113257

  • Kód UT WoS článku

    000993162200001

  • EID výsledku v databázi Scopus

    2-s2.0-85145561746