Zobrazeno 1 - 10
of 101
pro vyhledávání: '"Siggers Mark"'
Given a graph $G$ and two graph homomorphisms $\alpha$ and $\beta$ from $G$ to a fixed graph $H$, the problem $H$-Recoloring asks whether there is a transformation from $\alpha$ to $\beta$ that changes the image of a single vertex at each step and ke
Externí odkaz:
http://arxiv.org/abs/2410.12687
A recent paper describes a framework for studying the computational complexity of graph problems on monotone classes, that is those omitting a set of graphs as a subgraph. If the problems lie in the framework, and many do, then the computational comp
Externí odkaz:
http://arxiv.org/abs/2403.00497
Gonz\'alez-Meneses, Manch\'on, and Silvero showed that the (hypothetical) extreme Khovanov homology of a link diagram is isomorphic to the reduced (co)homology of the independence simplicial complex of its Lando graph. Przytycki and Silvero conjectur
Externí odkaz:
http://arxiv.org/abs/2401.06487
Autor:
Lozin, Vadim, Martin, Barnaby, Pandey, Sukanya, Paulusma, Daniel, Siggers, Mark, Smith, Siani, van Leeuwen, Erik Jan
For a fixed set ${\cal H}$ of graphs, a graph $G$ is ${\cal H}$-subgraph-free if $G$ does not contain any $H \in {\cal H}$ as a (not necessarily induced) subgraph. A recently proposed framework gives a complete classification on ${\cal H}$-subgraph-f
Externí odkaz:
http://arxiv.org/abs/2211.14214
Autor:
Siggers, Mark
In 2000, Brightwell and Winkler characterised dismantlable graphs as the graphs $H$ for which the Hom-graph ${\rm Hom}(G,H)$, defined on the set of homomorphisms from $G$ to $H$, is connected for all graphs $G$. This shows that the reconfiguration ve
Externí odkaz:
http://arxiv.org/abs/2208.04071
Publikováno v:
European Journal of Combinatorics 2024
In the problem ${\rm Mix}(H)$ one is given a graph $G$ and must decide if the Hom-graph ${\rm {\bf Hom}}(G,H)$ is connected. We show that if $H$ is a triangle-free reflexive graph with at least one cycle, ${\rm Mix}(H)$ is ${\rm coNP}$-complete. The
Externí odkaz:
http://arxiv.org/abs/2207.03632
Publikováno v:
J Algebr Comb, 57, (2022) pp. 53--73
For a graph $H$, the $H$-recolouring problem $\operatorname{Recol}(H)$ asks, for two given homomorphisms from a given graph $G$ to $H$, if one can get between them by a sequence of homomorphisms of $G$ to $H$ in which consecutive homomorphisms differ
Externí odkaz:
http://arxiv.org/abs/2111.00723
Autor:
Kim, Hyobin, Siggers, Mark
Publikováno v:
Kyungpook Math. J. 63(2023), pp. 355-372
We make advances towards a structural characterisation of the signed graphs $H$ for which the list switch $H$-colouring problem $\operatorname{LSwHom}(H)$ problem is polynomial time solvable. We conjecture a characterisation for signed graphs that ca
Externí odkaz:
http://arxiv.org/abs/2104.07764
Publikováno v:
In European Journal of Combinatorics February 2024 116
Publikováno v:
European J. Combin. 86 (2020) 103086
Given a loop-free graph $H$, the reconfiguration problem for homomorphisms to $H$ (also called $H$-colourings) asks: given two $H$-colourings $f$ of $g$ of a graph $G$, is it possible to transform $f$ into $g$ by a sequence of single-vertex colour ch
Externí odkaz:
http://arxiv.org/abs/1810.01111