Geodesic
A note about monochromatic components in graphs of large minimum degree
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 607-618 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

For all positive integers r≥ 3 and n such that r^2-r 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-2r^2-r)n-2 such that the largest monochromatic component has order less than nr-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: Ramsey theory, fractional matchings, block designs 
@article{DMGT_2023_43_3_a1,
     author = {DeBiasio, Louis and Krueger, Robert A.},
     title = {A note about monochromatic components in graphs of large minimum degree},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {607--618},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a1/}
}
TY  - JOUR
AU  - DeBiasio, Louis
AU  - Krueger, Robert A.
TI  - A note about monochromatic components in graphs of large minimum degree
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 607
EP  - 618
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a1/
LA  - en
ID  - DMGT_2023_43_3_a1
ER  - 
%0 Journal Article
%A DeBiasio, Louis
%A Krueger, Robert A.
%T A note about monochromatic components in graphs of large minimum degree
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 607-618
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a1/
%G en
%F DMGT_2023_43_3_a1
DeBiasio, Louis; Krueger, Robert A. A note about monochromatic components in graphs of large minimum degree. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 607-618. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a1/

[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).

[2] Y. Chang, The existence of resolvable BIBD with \lambda=1, Acta Math. Appl. Sin. 16 (2000) 373–385. https://doi.org/10.1007/BF02671127

[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. https://doi.org/10.1002/jgt.22510

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

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

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

[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. https://doi.org/10.37236/7049

[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. https://doi.org/10.1017/S0963548311000599

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

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

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

[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. https://doi.org/10.1016/B978-0-7204-2262-7.50035-1