Back to Search
Start Over
Tree decompositions of graphs without large bipartite holes
- Source :
- Random Structures & Algorithms. 57:150-168
- Publication Year :
- 2020
- Publisher :
- Wiley, 2020.
-
Abstract
- A recent result of Condon, Kim, K\"{u}hn and Osthus implies that for any $r\geq (\frac{1}{2}+o(1))n$, an $n$-vertex almost $r$-regular graph $G$ has an approximate decomposition into any collections of $n$-vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost $\alpha n$-regular graph $G$ with any $\alpha>0$ and a collection of bounded degree trees on at most $(1-o(1))n$ vertices if $G$ does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into $n$-vertex trees. Moreover, this implies that for any $\alpha>0$ and an $n$-vertex almost $\alpha n$-regular graph $G$, with high probability, the randomly perturbed graph $G\cup \mathbf{G}(n,O(\frac{1}{n}))$ has an approximate decomposition into all collections of bounded degree trees of size at most $(1-o(1))n$ simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey-Tur\'an theory and the randomly perturbed graph model.<br />Comment: 15 pages
- Subjects :
- Spanning tree
Degree (graph theory)
Applied Mathematics
General Mathematics
010102 general mathematics
Context (language use)
0102 computer and information sciences
01 natural sciences
Computer Graphics and Computer-Aided Design
Tree decomposition
Graph
Combinatorics
Tree (descriptive set theory)
010201 computation theory & mathematics
Bounded function
FOS: Mathematics
Bipartite graph
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Software
Mathematics
Subjects
Details
- ISSN :
- 10982418 and 10429832
- Volume :
- 57
- Database :
- OpenAIRE
- Journal :
- Random Structures & Algorithms
- Accession number :
- edsair.doi.dedup.....de207af8ef6649f9fd5291b794ae9c07