A Note About Monochromatic Components in Graphs of Large Minimum Degree
A Note About Monochromatic Components in Graphs of Large Minimum Degree
复制标题
DOI：
10.7151/dmgt.2390
复制
发表时间：
2020-06
影响因子：
0.7
通讯作者：
Louis DeBiasio;Robert A. Krueger
中科院分区：
文献类型：
--
作者：
Louis DeBiasio;Robert A. Krueger
对所有的正整数r ≥ 3和n使得r2-r整除n且存在r阶仿射平面，构造了一个n阶最小度为（1-r-2 r2-r{{r - 2} \over {{r^2} - r}}）n-2的r-边着色图，使得最大单色分量的阶数小于nr-1{n \over {r - 1}}.这推广了Guggiari和Scott以及Rahimi对于r = 3的一个例子，从而反驳了Gyárfás和Sárközy对于所有整数r ≥ 3使得存在r阶仿射平面的猜想。
Abstract 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.