Tight bounds for divisible subdivisions

DOI10.1016/J.JCTB.2023.10.011zbMATH Open1530.05177arXiv2111.05723OpenAlexW3211901379MaRDI QIDQ6187340FDOQ6187340

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)

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.

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)

Cites Work

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

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)