You are here
The Relaxed Square Property
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
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.
Journal:
Australasian Journal of Combinatorics
Publication Date:
11 Jul 2014
Citation:
[HMO+15]
Hellmuth, M., Marc, T., Ostermeier, L., and Stadler, P. F.: The Relaxed Square Property.
Australasian Journal of Combinatorics, 62, 3, 240-270, 2015
Researchers:
- Log in to post comments