Clique factors in pseudorandom graphs

被引:0
作者
Morris, Patrick [1 ]
机构
[1] Univ Politecn Cataluna, Dept Math, Barcelona, Spain
关键词
Pseudorandom graphs; clique factors; extremal graph theory; TRIANGLE-FACTORS; MATCHINGS; CONJECTURES; HYPERGRAPHS; PACKINGS; SEQUENCE; NUMBER;
D O I
10.4171/JEMS/1388
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
An n-vertex graph is said to to be (p, )-bijumbled if for any vertex sets A, B C V(G), we have p e(A, B subset of = V(G) , e(A, B) = p|A|B| +/- beta root|A| |B|. We prove that for any r is an element of N >= 3 and c > 0 there exists an e > 0 such that any n-vertex (p, beta)- bijumbled graph with n is an element of rN, p > 0, delta(G) > cpn and <= epsilon p(r-1)n contains a K-r-factor. This implies a corresponding result for the stronger pseudorandom notion of (n, d, lambda)-graphs. For the case of triangle factors, that is, when r = 3, this result resolves a conjecture of Krivelevich, Sudakov and Szab & oacute; from 2004 and it is tight due to a pseudorandom triangle-free construction of Alon. In fact, in this case even more is true: as a corollary to this result and a result of Han, Kohayakawa, Person and the author, we can conclude that the same condition of beta = o(p(2)n) actually guarantees that a (p, beta)-bijumbled graph G contains every graph on n vertices with maximum degree at most 2.
引用
收藏
页码:801 / 875
页数:75
相关论文
共 50 条
[41]   Clique-Coloring of K3,3-Minor Free Graphs [J].
Omoomi, Behnaz ;
Taleb, Maryam .
BULLETIN OF THE IRANIAN MATHEMATICAL SOCIETY, 2020, 46 (06) :1539-1550
[42]   Homogeneous sets, clique-separators, critical graphs, and optimal X -binding functions [J].
Brause, Christoph ;
Geisser, Maximilian ;
Schiermeyer, Ingo .
DISCRETE APPLIED MATHEMATICS, 2022, 320 :211-222
[43]   Clique-transversal sets in 4-regular claw-free graphs [J].
Shan, Er Fang ;
Kang, Li Ying .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2011, 27 (05) :883-890
[44]   Even factors of graphs [J].
Jian Cheng ;
Cun-Quan Zhang ;
Bao-Xuan Zhu .
Journal of Combinatorial Optimization, 2017, 33 :1343-1353
[45]   Even factors of graphs [J].
Cheng, Jian ;
Zhang, Cun-Quan ;
Zhu, Bao-Xuan .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (04) :1343-1353
[46]   Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs [J].
H. B. Macêdo Filho ;
R. C. S. Machado ;
C. M. H. de Figueiredo .
Algorithmica, 2017, 77 :786-814
[47]   Packing tree factors in random and pseudo-random graphs [J].
Bal, Deepak ;
Krivelevich, Michael ;
Frieze, Alan ;
Loh, Po-Shen .
ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (02)
[48]   On the triangle clique cover and Kt clique cover problems [J].
Dau, Hoang ;
Milenkovic, Olgica ;
Puleo, Gregory J. .
DISCRETE MATHEMATICS, 2020, 343 (0I)
[49]   Some results and problems on clique coverings of hypergraphs [J].
Rodl, Vojtech ;
Sales, Marcelo .
JOURNAL OF GRAPH THEORY, 2024, 107 (02) :442-457
[50]   Eigenvalues and [ a , b ]-factors in regular graphs [J].
Suil, O. .
JOURNAL OF GRAPH THEORY, 2022, 100 (03) :458-469