z-logo
open-access-imgOpen Access
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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom