The Library
Disjoint isomorphic balanced clique subdivisions
Tools
Gil Fernandez, I., Hyde, J., Liu, H., Pikhurko, O. and Wu, Z. (2023) Disjoint isomorphic balanced clique subdivisions. Journal of Combinatorial Theory, Series B, 161 . pp. 417-436. doi:10.1016/j.jctb.2023.03.002 ISSN 0095-8956.
|
PDF
WRAP-disjoint-isomorphic-balanced-clique-subdivisions-Pikhurko-2023.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (461Kb) | Preview |
Official URL: https://doi.org/10.1016/j.jctb.2023.03.002
Abstract
A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that there is a constant C such that every graph with average degree at least has a subdivision of , the complete graph on k vertices. We study two directions extending this result. • Verstraëte conjectured that a quadratic bound guarantees in fact two vertex-disjoint isomorphic copies of a -subdivision.
• Thomassen conjectured that for each there is some such that every graph with average degree at least d contains a balanced subdivision of . Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on remains open. In this paper, we show that a quadratic lower bound on average degree suffices to force a balanced -subdivision. This gives the right order of magnitude of the optimal needed in Thomassen's conjecture. Since a balanced -subdivision trivially contains m vertex-disjoint isomorphic -subdivisions, this also confirms Verstraëte's conjecture in a strong sense.
Item Type: | Journal Article | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||||||
Journal or Publication Title: | Journal of Combinatorial Theory, Series B | ||||||||||||
Publisher: | Elsevier | ||||||||||||
ISSN: | 0095-8956 | ||||||||||||
Official Date: | July 2023 | ||||||||||||
Dates: |
|
||||||||||||
Volume: | 161 | ||||||||||||
Page Range: | pp. 417-436 | ||||||||||||
DOI: | 10.1016/j.jctb.2023.03.002 | ||||||||||||
Status: | Peer Reviewed | ||||||||||||
Publication Status: | Published | ||||||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||||||
Date of first compliant deposit: | 11 April 2023 | ||||||||||||
Date of first compliant Open Access: | 11 April 2023 | ||||||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year