dc.contributor.author
Botler, F.
dc.contributor.author
Naia, Tássio
dc.date.accessioned
2025-06-19T09:53:31Z
dc.date.available
2025-06-19T09:53:31Z
dc.date.issued
2025-04-10
dc.identifier.uri
http://hdl.handle.net/2072/484458
dc.description.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.).
ca
dc.description.sponsorship
This study has been partially supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior ‐ Brasil ‐ CAPES ‐ Finance Code 001.Fábio Botler is supported by CNPq (304315/2022‐2) and CAPES (88881.973147/2024‐01). Tássio Naia was supported by the Grant PID2020‐113082GB‐I00funded by MICIU/AEI/10.13039/501100011033 and by the Spanish State Research Agency, through the Severo Ochoa and María de Maeztu Program forCenters and Units of Excellence in R&D (CEX2020‐001084‐M). CNPq is the National Council for Scientific and Technological Development of Brazil.
ca
dc.publisher
John Wiley and Sons
ca
dc.relation.ispartof
Journal of Graph Theory
ca
dc.rights
Attribution 4.0 International
*
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
*
dc.source
RECERCAT (Dipòsit de la Recerca de Catalunya)
dc.subject.other
Graph
ca
dc.subject.other
Separating system
ca
dc.subject.other
Subdivision
ca
dc.title
Separating the Edges of a Graph by Cycles and by Subdivisions of K4
ca
dc.type
info:eu-repo/semantics/article
ca
dc.description.version
info:eu-repo/semantics/publishedVersion
ca
dc.identifier.doi
10.1002/jgt.23248
ca
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
