Zobrazeno 1 - 10
of 93
pro vyhledávání: '"Zeman, Peter"'
Man\v{c}inska and Roberson~[FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al.~[JCTB'19] proved that quantum isomorphism is undecidable in gen
Externí odkaz:
http://arxiv.org/abs/2407.10635
Autor:
Árnadóttir, Arnbjörg Soffía, de Bruyn, Josse van Dobben, Kar, Prem Nigam, Roberson, David E., Zeman, Peter
Sabidussi's theorem [Duke Math. J. 28, 1961] gives necessary and sufficient conditions under which the automorphism group of a lexicographic product of two graphs is a wreath product of the respective automorphism groups. We prove a quantum version o
Externí odkaz:
http://arxiv.org/abs/2402.12344
Autor:
de Bruyn, Josse van Dobben, Kar, Prem Nigam, Roberson, David E., Schmidt, Simon, Zeman, Peter
We give a characterisation of quantum automorphism groups of trees. In particular, for every tree, we show how to iteratively construct its quantum automorphism group using free products and free wreath products. This can be considered a quantum vers
Externí odkaz:
http://arxiv.org/abs/2311.04891
Let $m$ be a positive integer, $X$ a graph with vertex set $\Omega$, and ${\rm WL}_m(X)$ the coloring of the Cartesian $m$-power $\Omega^m$, obtained by the $m$-dimensional Weisfeiler-Leman algorithm. The ${\rm WL}$-dimension of the graph $X$ is defi
Externí odkaz:
http://arxiv.org/abs/2305.17302
Autor:
Çağırıcı, Deniz Ağaoğlu, Çağırıcı, Onur, Derbisz, Jan, Hartmann, Tim A., Hliněný, Petr, Kratochvíl, Jan, Krawczyk, Tomasz, Zeman, Peter
In 1992 Bir\'{o}, Hujter and Tuza introduced, for every fixed connected graph $H$, the class of $H$-graphs, defined as the intersection graphs of connected subgraphs of some subdivision of $H$. Recently, quite a lot of research has been devoted to un
Externí odkaz:
http://arxiv.org/abs/2212.05433
Autor:
Çağırıcı, Deniz Ağaoğlu, Zeman, Peter
An $H$-graph is an intersection graph of connected subgraphs of a suitable subdivision of a fixed graph $H$. Many important classes of graphs, including interval graphs, circular-arc graphs, and chordal graphs, can be expressed as $H$-graphs, and, in
Externí odkaz:
http://arxiv.org/abs/2206.13372
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as the first example of a graph class where the recognition is polynomia
Externí odkaz:
http://arxiv.org/abs/2108.13076
The computational complexity of the graph isomorphism problem is considered to be a major open problem in theoretical computer science. It is known that testing isomorphism of chordal graphs is polynomial-time equivalent to the general graph isomorph
Externí odkaz:
http://arxiv.org/abs/2107.10689
By a map we mean a $2$-cell decomposition of a closed compact surface, i.e., an embedding of a graph such that every face is homeomorphic to an open disc. Automorphism of a map can be thought of as a permutation of the vertices which preserves the ve
Externí odkaz:
http://arxiv.org/abs/2008.01616
Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)\alpha(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and
Externí odkaz:
http://arxiv.org/abs/1908.09151