1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

A Note About Monochromatic Components in Graphs of Large Minimum Degree

Published Online: 24 Feb 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 24 Jul 2020
Accepted: 11 Dec 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

For all positive integers r ≥ 3 and n such that r2r divides n and an affine plane of order r exists, we construct an r-edge colored graph on n vertices with minimum degree (1−r-2r2-r{{r - 2} \over {{r^2} - r}})n−2 such that the largest monochromatic component has order less than nr-1{n \over {r - 1}}. This generalizes an example of Guggiari and Scott and, independently, Rahimi for r = 3 and thus disproves a conjecture of Gyárfás and Sárközy for all integers r ≥ 3 such that an affine plane of order r exists.

Keywords

MSC 2010

[1] R.J.R. Abel, G. Ge and J. Yin, Resolvable and Near-Resolvable Designs, in: Handbook of Combinatorial Designs, C. Colbourn and J. Dinitz, (Ed(s)), (Chapmann & Hall/CRC, Boca Raton, 1996).Search in Google Scholar

[2] Y. Chang, The existence of resolvable BIBD withλ = 1, Acta Math. Appl. Sin. 16 (2000) 373–385. doi:10.1007/BF0267112710.1007/BF02671127Search in Google Scholar

[3] L. DeBiasio, R.A. Krueger and G.N. Sárközy, Large monochromatic components in multicolored bipartite graphs, J. Graph Theory 94 (2020) 117–130. doi:10.1002/jgt.2251010.1002/jgt.22510Search in Google Scholar

[4] Z. Füredi, Covering the complete graph by partitions, Discrete Math. 75 (1989) 217–226. doi:10.1016/0012-365X(89)90088-510.1016/0012-365X(89)90088-5Search in Google Scholar

[5] H. Guggiari and A. Scott, Monochromatic components in edge-coloured graphs with large minimum degree. arXiv:1909.09178v1 (2019)Search in Google Scholar

[6] A. Gyárfás, Partition coverings and blocking sets in hypergraphs, Commun. Comput. Autom. Inst. Hungar. Acad. Sci. 71 (1977), in Hungarian.Search in Google Scholar

[7] A. Gyárfás and G.N. Sárközy, Large monochromatic components in edge colored graphs with a minimum degree condition, Electron. J. Combin. 24 (2017) #P3.54. doi:10.37236/704910.37236/7049Search in Google Scholar

[8] A. Gyárfás and G.N. Sárközy, Star versus two stripes Ramsey numbers and a conjecture of Schelp, Combin. Probab. Comput. 21 (2012) 179–186. doi:10.1017/S096354831100059910.1017/S0963548311000599Search in Google Scholar

[9] L. Lovász and M.D. Plummer, Matching Theory (AMS Chelsea Publishing, Providence, 2009). doi:10.1090/chel/36710.1090/chel/367Search in Google Scholar

[10] R.A. Mathon, K.T. Phelps and A. Rosa, Small Steiner triple systems and their properties, Ars Combin. 15 (1983) 3–110.Search in Google Scholar

[11] Z. Rahimi, Large monochromatic components in 3-colored non-complete graphs, J. Combin. Theory Ser. A 175 (2020) 105256. doi:10.1016/j.jcta.2020.10525610.1016/j.jcta.2020.105256Search in Google Scholar

[12] D.K. Ray-Chaudhuri and R.M. Wilson, The existence of resolvable block designs, in: A Survey of Combinatorial Theory (North-Holland, 1973) 361–375. doi:10.1016/B978-0-7204-2262-7.50035-110.1016/B978-0-7204-2262-7.50035-1Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo