Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-23T14:06:12.607Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangle-Tilings in Graphs Without Large Independent Sets

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  09 May 2018

JÓZSEF BALOGH ,
ANDREW McDOWELL ,
THEODORE MOLLA  and
RICHARD MYCROFT
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801, USA (e-mail: [email protected])
ANDREW McDOWELL
Affiliation:
Informatics Department, King's College London, London WC2R 2LS, UK (e-mail: [email protected])
THEODORE MOLLA
Affiliation:
University of South Florida, Tampa, FL 33620, USA (e-mail: [email protected])
RICHARD MYCROFT
Affiliation:
School of Mathematics, University of Birmingham, Birmingham B15 2TT, UK (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

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 δ(G) ≥ n/3 + o(n), then G has a triangle-tiling covering all but at most four vertices. Also, for every r ≥ 5, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that G is Kr-free and n is divisible by 3.

MSC classification

Primary: 05C35: Extremal problems
Secondary: 05C70: Factorization, matching, partitioning, covering and packing 05D40: Probabilistic methods
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Special Issue 4: Special Issue: Oberwolfach Workshop , July 2018 , pp. 449 - 474
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Balogh, J., Molla, T. and Sharifzadeh, M. Triangle factors of graphs without large independent sets and of weighed graphs. Random Struct. Alg. Proc. of the Seventeenth International Conference “Random Structures and Algorithms" held 27–31 July, 2015, Pittsburgh, USA: 49 669–693.Google Scholar
[2] Bollobás, B. and Erdős, P. (1976) On a Ramsey–Turán type problem. J. Combin. Theory Ser. B 21 166–168.Google Scholar
[3] Corrádi, K. and Hajnal, A. (1963) On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hungar. 14 423–439.Google Scholar
[4] Csaba, B. and Mydlarz, M. (2012) On the maximal number of independent circuits in a graph. J. Combin. Theory Ser. B 102 395–410.Google Scholar
[5] Enomoto, H., Kaneko, A. and Tuza, Z. (1987) P 3-factors and covering cycles in graphs of minimum degree n/3. In Combinatorics (Eger, 1987), Vol. 52 of Colloq. Math. Soc. János Bolyai, pp. 213–220.Google Scholar
[6] Erdős, P. (1961) Graph theory and probability II. Canad. J. Math. 13 346–352.Google Scholar
[7] Erdős, P., Hajnal, A., Sós, V. T. and Szemerédi, E. (1983) More results on Ramsey–Turán type problems. Combinatorica 3 69–81.CrossRefGoogle Scholar
[8] Erdős, P. and Sós, V. T. (1970) Some remarks on Ramsey's and Turán's theorems. In Combinatorial Theory and its Applications (Proc. Colloq., Balatonfüred, 1969), János Bolyai Mathematical Society, pp. 395–404.Google Scholar
[9] Janson, S., Łuczak, T. uczak, T. and Ruciński, A. (2000) Random Graphs, Wiley-Interscience.Google Scholar
[10] Kohayakawa, Y. and Rödl, V. (2003) Szemerédi's Regularity Lemma and quasi-randomness. In Recent Advances in Algorithms and Combinatorics (Reed, B. A. and Sales, C. L., eds), Springer, pp. 289–351.Google Scholar
[11] Komlós, J., Sárközy, G. and Szemerédi, E. (1997) Blow-up lemma. Combinatorica 17 109–123.Google Scholar
[12] Komlós, J. and Simonovits, M. (1996) Szemerédi's Regularity Lemma and its applications in graph theory. In Combinatorics: Paul Erdős is Eighty (Keszthely, 1993), Vol. 2 of Bolyai Society Mathematical Studies, János Bolyai Mathematical Society, pp. 295–352.Google Scholar
[13] Martin, R. and Skokan, J. (2013) Asymptotic multipartite version of the Alon–Yuster theorem. J. Combin. Theory Ser. B 127 33–52.Google Scholar
[14] Rödl, V. and Ruciński, A. (1999) Perfect matchings in ϵ-regular graphs and the Blow-up Lemma. Combinatorica 19 437–452.Google Scholar
[15] Szemerédi, E. (1972) On graphs containing no complete subgraph with 4 vertices (in Hungarian). Mat. Lapok 23 111–116.Google Scholar
[16] Win, S. (1975) Existenz von Gerüsten mit vorgeschreibenem Maximalgrad in Graphen. Abh. Math. Sem. Univ. Hamburg 43 263–267.CrossRefGoogle Scholar