Finding Large p-Colored Diameter Two Subgraphs |
| |
Authors: | Paul Erdo˝s Tom Fowler |
| |
Institution: | (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 k\2hphk 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<k\2. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|