Back to Search
Start Over
Triangle-tilings in graphs without large independent sets
- Publication Year :
- 2016
- Publisher :
- arXiv, 2016.
-
Abstract
- We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an $n$-vertex graph $G$ with sublinear independence number. In this setting, we show that if $\delta(G) \ge n/3 + o(n)$ then $G$ has a triangle-tiling covering all but at most four vertices. Also, for every $r \ge 5$, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that $G$ is $K_r$-free and $n$ is divisible by $3$.<br />Comment: 24 pages
- Subjects :
- Statistics and Probability
Degree (graph theory)
Sublinear function
Applied Mathematics
05C70
010102 general mathematics
0102 computer and information sciences
16. Peace & justice
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
010201 computation theory & mathematics
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics
Independence number
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....1cee80a5b30603bb7f27bed3cd3330ff
- Full Text :
- https://doi.org/10.48550/arxiv.1607.07789