DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

L. DeBiasio

Louis DeBiasio

email: debiasld@miamioh.edu

R.A. Krueger

Robert Krueger

University of Illinois at Urbana-Champaign

email: rak5@illinois.edu

Title:

A note about monochromatic components in graphs of large minimum degree

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 607-618

Received: 2020-07-24 , Revised: 2020-12-11 , Accepted: 2020-12-11 , Available online: 2021-01-14 , https://doi.org/10.7151/dmgt.2390

Abstract:

For all positive integers $r\geq 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-\frac{r-2}{r^2-r})n-2$ such that the largest monochromatic component has order less than $\frac{n}{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"ozy for all integers $r\geq 3$ such that an affine plane of order $r$ exists.

Keywords:

Ramsey theory, fractional matchings, block designs

References:

  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
Close