Monochromatic diameter-2 components in edge colorings of the complete graph (Q2233352)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Monochromatic diameter-2 components in edge colorings of the complete graph |
scientific article |
Statements
Monochromatic diameter-2 components in edge colorings of the complete graph (English)
0 references
18 October 2021
0 references
\textit{A. Gyárfás} [Prog. Math. 285, 77--96 (2011; Zbl 1221.05140), Problem 4.3] posed the following problem. Problem. Given positive numbers \(n\), \(r\), is there a constant \(d\) (perhaps \(d = 3\)) such that in every \(r\)-coloring of \(K_n\) there is a monochromatic subgraph of diameter at most \(d\) with at least \(n/ (r-1)\) vertices? By proving the following theorems, the authors show that for \(r = 3; 4; 5\) and 6 a diameter of 3 is best possible in this conjecture. There exists a 3-edge-coloring of \(K_n\) with the largest monochromatic diameter \(\leq 2\) subgraph of size \(\leq 3 \lceil n/7 \rceil\). There exists a 4-edge-coloring of \(K_n\) with the largest monochromatic diameter \(\leq 2\) subgraph of size \(\leq 5 \lceil n/17 \rceil\). There exists a 5-edge-coloring of \(K_n\) with the largest monochromatic diameter \(\leq 2\) subgraph of size \(\leq 7 \lceil n/31 \rceil\). There exists a 6-edge-coloring of \(K-n\) with the largest monochromatic diameter \(\leq 2\) subgraph of size \(\leq 9 \lceil n/47 \rceil\). The following conjecture is stated. Conjecture. For arbitrary number of colors \(r\), the size of the largest monochromatic diameter-2 subgraph existing in every \(r\) coloring of \(K_n\) is significantly less than the size of the largest monochromatic diameter-4 subgraph existing in every \(r\)-coloring of \(K_n\).
0 references
Ramsey theory
0 references
edge colorings
0 references
graph theory
0 references
combinatorics
0 references
monochromatic components
0 references
graph factorization
0 references