Finding Large p-Colored Diameter Two Subgraphs |
| |
Authors: | Paul Erdo˝s Tom Fowler |
| |
Affiliation: | (1) Department of Mathematics, University of Florida, Gainesville, FL 32611, USA |
| |
Abstract: | Given a coloring of the edges of the complete graph K on n vertices in k colors, a p-colored subgraph of Kn is any subgraph whose edges only use colors from some p element set. We show for k̿ and k2hphk that there is always a p-colored diameter two subgraph of Kn containing at least [((k+p)n)/(2k)]displaystyle{(k+p)n over 2k} vertices and that this is best possible up to an additive constant l satisfying 0hl<k2. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|