Local conditions for exponentially many subdivisions

DOI10.1017/S0963548316000365MaRDI QIDQ5366949zbMATH OpenOpenAlexFDO

Authors Hong Liu, Maryam Sharifzadeh, Katherine Staden

Publication date 10 October 2017

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

distinguishable cycles

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Graph minors (05C83)

Abstract: Given a graph $F$, let $s_t(F)$ be the number of subdivisions of $F$, each with a different vertex set, which one can guarantee in a graph $G$ in which every edge lies in at least $t$ copies of $F$. In 1990, Tuza asked for which graphs $F$ and large $t$, one has that $s_t(F)$ is exponential in a power of $t$. We show that, somewhat surprisingly, the only such $F$ are complete graphs, and for every $F$ which is not complete, $s_t(F)$ is polynomial in $t$. Further, for a natural strengthening of the local condition above, we also characterise those $F$ for which $s_t(F)$ is exponential in a power of $t$.

Recommendations

• The extremal number of longer subdivisions
• The extremal number of the subdivisions of the complete bipartite graph
• Subdivision thresholds for two classes of graphs
• Compact topological minors in graphs
• Turán numbers of subdivided graphs

Cites work

• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Extremal connectivity for topological cliques in bipartite graphs
• Highly linked graphs
• Hinreichende Bedingungen für die Existenz von Teilgraphen, die zu einem vollständigen Graphen homöomorph sind
• scientific article; zbMATH DE number 26333 (Why is no real title available?)
• Problems on cycles and colorings
• Topological cliques in graphs II

Cited in

(1)

• scientific article; zbMATH DE number 5270874 (Why is no real title available?)

This page was built for publication: Local conditions for exponentially many subdivisions

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