Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs (Q1260770)

From MaRDI portal
Revision as of 09:31, 31 January 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs
scientific article

    Statements

    Ramsey problems involving degrees in edge-colored complete graphs of vertices belonging to monochromatic subgraphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    25 August 1993
    0 references
    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\).
    0 references
    monochromatic subgraphs
    0 references
    coloring
    0 references
    Ramsey's theorem
    0 references

    Identifiers