Finding Large Monochromatic Diameter Two Subgraphs

Simple item page
dc.creatorFowler, Tom
dc.date1999-08-30
dc.date.accessioned2026-07-07T05:30:35Z
dc.date.available2026-07-07T05:30:35Z
dc.descriptionGiven a coloring of the edges of the complete graph on n vertices in k colors, by considering the neighbors of an arbitrary vertex it follows that there is a monochromatic diameter two subgraph on at least 1+(n-1)/k vertices. We show that for $k \ge 3$ this is asymptotically best possible, and that for k=2 there is always a monochromatic diameter two subgraph on at least $\lceil {3 \over 4} n \rceil$ vertices, which again, is best possible.
dc.description20 pages
dc.identifierhttps://arxiv.org/abs/math/9908170
dc.identifierhttp://arxiv.org/abs/math/9908170
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/79036
dc.subjectCombinatorics
dc.titleFinding Large Monochromatic Diameter Two Subgraphs
dc.typetext

Files

Collections

arXiv