Publications - Published papers
Please find below publications of our group. Currently, we list 565 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:
) is restricted to our local network and chosen collaborators.
If you have problems accessing electronic information, please let us know:©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.
The relaxed square property
Hellmuth, Marc and Marc, Tilen and Ostermeier, Lydia and Stadler, Peter F.
Download
Status: Published
Australasian Journal of Combinatorics Vol 62: No. 3 240-770 (2015)
Abstract
Graph products are characterized by the existence of non-trivial
equivalence relations on the edge set of a graph that satisfy a so-called
square property. We investigate here a generalization, termed
\emph{RSP-relations}. The class of graphs with non-trivial RSP-relations
in particular includes graph bundles. Furthermore, RSP-relations are
intimately related with covering graph constructions. For $K_{2,3}$-free
graphs finest RSP-relations can be computed in polynomial-time. In
general, however, they are not unique and their number may even grow
exponentially. They behave well for graph products, however, in sense that
a finest RSP-relation can be obtained easily from finest RSP-relations on
the prime factors.