Separating the Edges of a Graph by Cycles and by Subdivisions of K4

Abstract

A separating system of a graph (Formula presented.) is a family (Formula presented.) of subgraphs of (Formula presented.) for which the following holds: for all distinct edges (Formula presented.) and (Formula presented.) of (Formula presented.), there exists an element in (Formula presented.) that contains (Formula presented.) but not (Formula presented.). Recently, it has been shown that every graph of order (Formula presented.) admits a separating system consisting of (Formula presented.) paths, improving the previous almost linear bound of (Formula presented.), and settling conjectures posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. We investigate a natural generalization of these results to subdivisions of cliques, showing that every graph admits both a separating system consisting of (Formula presented.) edges and cycles and a separating system consisting of (Formula presented.) edges and subdivisions of (Formula presented.).