Graphs with Monochromatic Complete Subgraphs in Every Edge Coloring

摘要

The report contains an investigation of a class of graphs G with the property that if the edges of G are colored red and blue, then either G contains r mutually adjacent vertices with all connecting lines colored red or s mutually adjacent vertices with all connecting lines colored blue. The study concerns the maximum number of mutually adjacent vertices that such a graph must have and shows that there exist graphs with only max(r, s) mutually adjacent vertices. (Author)