A note about monochromatic components in graphs of large minimum degree
Author(s) -
Louis DeBiasio,
Robert A. Krueger
Publication year - 2021
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2390
Subject(s) - mathematics , degree (music) , combinatorics , monochromatic color , discrete mathematics , botany , physics , acoustics , biology
For all positive integers r ≥ 3 and n such that r2 − 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-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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom