# Large monochromatic components of small diameter

@article{Carlson2021LargeMC, title={Large monochromatic components of small diameter}, author={Erik Carlson and Ryan R. Martin and Bo Peng and Mikl'os Ruszink'o}, journal={Journal of Graph Theory}, year={2021} }

Gyárfás [4] conjectured in 2011 that every r-edge-colored Kn contains a monochromatic component of bounded (“perhaps three”) diameter on at least n/(r−1) vertices. Letzter [6] proved this conjecture with diameter four. In this note we improve the result in the case of r = 3: We show that in every 3-edge-coloring of Kn either there is a monochromatic component of diameter at most three on at least n/2 vertices or every color class is spanning and has diameter at most four. 1 Monochromatic… Expand

#### References

SHOWING 1-10 OF 10 REFERENCES

Monochromatic diameter-2 components in edge colorings of the complete graph

- Mathematics
- Involve, a Journal of Mathematics
- 2021

Gyarfas conjectured that in every r -edge-coloring of the complete graph K n there is a monochromatic component on at least n ∕ ( r − 1 ) vertices which has diameter at most 3. We show that for r = 3… Expand

Size of Monochromatic Double Stars in Edge Colorings

- Mathematics, Computer Science
- Graphs Comb.
- 2008

It is shown that in every r-coloring of the edges of Kn there is a monochromatic double star with at least n(r+1)+r-1}{r^2+1} vertices, which improves a bound of Mubayi for the largest monochromeatic subgraph of diameter at most three. Expand

Large components in r-edge-colorings of Kn have diameter at most five

- Mathematics, Computer Science
- J. Graph Theory
- 2012

It is shown in this note that every r-edge-coloring of Kn contains a monochromatic component of diameter at most five on at least n/(r−1) vertices. Expand

Large Monochromatic Triple Stars in Edge Colourings

- Mathematics, Computer Science
- J. Graph Theory
- 2015

It is proved that for every r-edge-colouring of Kn there is a monochromatic triple star of order at least n/r-1, improving Ruszinko's result 2012. Expand

Covering the complete graph by partitions

- Computer Science, Mathematics
- Discret. Math.
- 1989

This work investigates the largest n such that K n has a ( D, c )-coloring, the main tool is the fractional matching theory of hypergraphs. Expand

Finding Large p-Colored Diameter Two Subgraphs

- Mathematics, Computer Science
- Graphs Comb.
- 1999

It is shown for k≥1 and k\2≤p≤k that there is always a p-colored diameter two subgraph of Kn containing at least vertices and that this is best possible up to an additive constant l satisfying 0≤l. Expand

Generalizing the Ramsey Problem through Diameter

- Mathematics, Computer Science
- Electron. J. Comb.
- 2002

The results include determining $f_1^k(K_n)$, which is equivalent to determining classical Ramsey numbers for multicolorings, and a construction due to Calkin implies that $f-3^k (K-n) \le {{n}\over {k-1}} + k-1$ when $k- 1$ is a prime power. Expand

Large Monochromatic Components in Edge Colorings of Graphs: A Survey

- Mathematics
- 2011

The aim of this survey is to summarize an area of combinatorics that lies on the border of several areas: Ramsey theory, resolvable block designs, factorizations, fractional matchings and coverings,… Expand

Partition coverings and blocking sets in hypergraphs (in Hungarian)

- vol. 71, Communications of the Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest
- 1977

Communications of the Computer and Automation Research Institute

- Hungarian)
- 1977