Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
type: Item
instance of: scholarly article
title: Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
zbMATH Open document ID: 0785.05067
author: Guantao Chen
author: Cecil Rousseau
author: R. H. Schelp
author: P. Erdős
published in: European Journal of Combinatorics
publication date: 1993-08-25T00:00:00Z
review text: This note concerns the degrees of vertices in the monochromatic subgraphs guaranteed by Ramseyian theorems. There are two theorems, using colorings \(g\) of edges into colors red and blue. Given a graph \(G\), let \(R\) be the graph of red edges and \(B\) the graph of blue edges. Let \(\deg_G(x)\) be the degree of the vertex \(x\) in \(G\). Given a regular graph \(G\) on vertices \(x\in X\), let \(\Delta_G=\max_{x\in X} \deg_G(x)- \min_{x\in X} \deg_G(x)\). If we color the edges of \(G\) red and blue, then \(\Delta_B=\Delta_R\), and we denote this common ``degree spread'' \(\Delta_\gamma\), where \(\gamma\) is the coloring. The first theorem is a formula for the minimal degree spread of vertices in the monochromatic subgraphs guaranteed by Ramsey's theorem. Given a graph \(G\) and a 2-coloring \(\gamma\) of its vertices, let \(\deg_R(x)\) be the degree of \(x\) in \(R\). The second theorem states that for any \(m\), if \(n=n(m)\) is sufficiently large, then any 2-coloring of the clique \(K_n\) admits a monochromatic bipartite \(K_{n,m}\) with two vertices \(x\) and \(y\) such that \(\deg_R(x)=\deg_R(y)\). This is also true of cycles \(C_m\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 370658
zbMATH Keywords: monochromatic subgraphs
zbMATH Keywords: coloring
zbMATH Keywords: Ramsey's theorem
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
full work available at URL: eujc.1993.1023
OpenAlex ID: W2071379313
Wikidata QID: Q105962094
DOI: 10.1006/EUJC.1993.1023
Recommended article: On monochromatic subgraphs of edge-colored complete graphs
Recommended article: Ramsey problem on multiplicities of complete subgraphs in nearly quasirandom graphs
Recommended article: Monochromatic-degree conditions for properly colored cycles in edge-colored complete graphs
Recommended article: A Ramsey type problem concerning vertex colourings
Recommended article: On the Ramsey multiplicity of complete graphs
Recommended article: Q4937803
Recommended article: Degree Ramsey numbers of graphs
Recommended article: Ramsey theory for highly connected monochromatic subgraphs
Recommended article: Set-coloring of edges and multigraph Ramsey numbers
Recommended article: Monochromatic components in edge-coloured graphs with large minimum degree
description: scientific article; zbMATH DE number 370658