Publications - Published papers

Please find below publications of our group. Currently, we list 508 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 (access) 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.


PREPRINT 15-045:
[ Publishers's page ]  paperID


Australasian Journal of Combinatorics Vol 62: No. 3 240-770 (2015)


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.