Tight bounds for divisible subdivisions

DOI10.1016/J.JCTB.2023.10.011MaRDI QIDQ6187340zbMATH OpenOpenAlexFDO

Authors Shagnik Das, Nemanja Draganić, Raphael Steiner

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

branch verticessubdivision pathssubdivision vertices

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph minors (05C83)

Abstract: Alon and Krivelevich proved that for every $n$-vertex subcubic graph $H$ and every integer $qge2$ there exists a (smallest) integer $f=f(H,q)$ such that every $K_f$-minor contains a subdivision of $H$ in which the length of every subdivision-path is divisible by $q$. Improving their superexponential bound, we show that $f(H,q)lefrac212qn+8n+14q$, which is optimal up to a constant multiplicative factor.

Recommendations

• Divisible subdivisions
• Improved bounds for the extremal number of subdivisions
• Subdivisions of graphs: A generalization of paths and cycles
• Compact topological minors in graphs
• The extremal number of longer subdivisions

Cites work

• scientific article; zbMATH DE number 1286510 (Why is no real title available?)
• scientific article; zbMATH DE number 887757 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A complete characterization of the zero-sum (mod 2) Ramsey numbers
• A solution to Erdős and Hajnal’s odd cycle problem
• Binomial coefficients and zero-sum Ramsey numbers
• Cycles Modulo k
• Dense minors in graphs of large girth
• Disjoint isomorphic balanced clique subdivisions
• Divisible subdivisions
• Expanders -- how to find them, and what to find in them
• Forcing a sparse minor
• Girth in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• Minors in graphs of large girth
• Note on coloring graphs without odd-\(K_k\)-minors
• ON ZERO SUM RAMSEY NUMBERS—COMPLETE GRAPHS
• On several variations of the turan and ramsey numbers
• On the odd-minor variant of Hadwiger's conjecture
• On three zero‐sum Ramsey‐type problems
• Problems in Zero-Sum Combinatorics
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Some Theorems on Abstract Graphs
• Some remarks on the odd Hadwiger's conjecture
• Stability critical graphs and even subdivisions of \(K_ 4\)
• Subdivisions of digraphs in tournaments
• The Graph Minor Algorithm with Parity Conditions
• The size‐Ramsey number of short subdivisions
• Topological cliques in graphs II
• Totally odd \(K_4\)-subdivisions in 4-chromatic graphs
• Totally odd subdivisions and parity subdivisions: structures and coloring
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Zero sum cycles in complete digraphs
• Zero-sum delta-systems and multiple copies of graphs
• Zero-sum problems -- a survey

Cited in

(1)

• Directed cycles with zero weight in \(\mathbb{Z}_p^k\)

This page was built for publication: Tight bounds for divisible subdivisions

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