Edge separators for graphs excluding a minor

DOI10.37236/11744MaRDI QIDQ6197318zbMATH OpenOpenAlexFDO

Authors Gwenaël Joret, William Lochet, Michał T. Seweryn

Publication date 16 February 2024

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.10998

zbMATH Keywords

bounded-genus graphsJacobi-Trudi identities for Foley-King factorial charactersline graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph operations (line graphs, products, etc.) (05C76) Graph minors (05C83)

Abstract: We prove that every $n$-vertex $K_t$-minor-free graph $G$ of maximum degree $Delta$ has a set $F$ of $O(t^2(logt{)}^{1/4}sqrtDeltan)$ edges such that every component of $G-F$ has at most $n/2$ vertices. This is best possible up to the dependency on $t$ and extends earlier results of Diks, Djidjev, Sykora, and Vrv{t}o (1993) for planar graphs, and of Sykora and Vrv{t}o (1993) for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of $G$ is isomorphic to a subgraph of the strong product $$ for some graph $H$ with treewidth at most $t-2$ and $p=sqrt(t-3)Delta|E(G)|+Delta$.

Review text

Summary: We prove that every \(n\)-vertex \(K_t\)-minor-free graph \(G\) of maximum degree \(\Delta\) has a set \(F\) of \(O(t^2(\log t)^{1/4}\sqrt{\Delta n})\) edges such that every component of \(G - F\) has at most \(n/2\) vertices. This is best possible up to the dependency on \(t\) and extends earlier results of \textit{K. Diks} et al. [J. Algorithms 14, No. 2, 258--279 (1993; Zbl 0764.68112)] for planar graphs, and of \textit{O. Sýkora} and \textit{I. Vrťo} [Theor. Comput. Sci. 112, No. 2, 419--429 (1993; Zbl 0772.05057)] for bounded-genus graphs. Our result is a consequence of the following more general result: The line graph of \(G\) is isomorphic to a subgraph of the strong product \(H \boxtimes K_{\lfloor p \rfloor}\) for some graph \(H\) with treewidth at most \(t-2\) and \(p = \sqrt{(t-3)\Delta |E(G)|} + \Delta\).

Recommendations

• Product structure of graphs with an excluded minor
• Edge separators for graphs of bounded genus with applications
• A Separator Theorem for Nonplanar Graphs
• scientific article; zbMATH DE number 219242
• Fast separation in a graph with an excluded minor

Cites work

• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• An extremal function for contractions of graphs
• Edge separators for graphs of bounded genus with applications
• Edge Separators of Planar and Outerplanar Graphs With Applications
• Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• Modularity of minor‐free graphs

Cited in

(1)

• Product structure of graphs with an excluded minor

This page was built for publication: Edge separators for graphs excluding a minor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6197318)