A new class of Ramsey-Turán problems (Q607020)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A new class of Ramsey-Turán problems
scientific article

    Statements

    A new class of Ramsey-Turán problems (English)
    0 references
    0 references
    0 references
    0 references
    19 November 2010
    0 references
    It is conjectured that if \(G\) is a \(2\)-edge colored graph of order \(n \geq 4\) with \(\delta(G) > 3n/4\), then there is for every integer \(4 \leq k \leq n/2\) a monochromatic \(C_k\). To support the conjecture it is proved that if \(G\) is a graph of order \(n\) sufficiently large with \(\delta(G) > 3n/4\), then for any \(\varepsilon > 0\) there is monochromatic \(C_k\) for \(4 \leq k \leq (1/8 - \varepsilon)n\) if \(G\) is \(2\)-edge colored. Examples are given to show that the minimum degree condition is sharp in the theorem, and it is also mentioned that a minimum degree condition of \(\delta(G) > 5n/4\) would be needed to get a monochromatic triangle.
    0 references
    Ramsey-Turán
    0 references
    minimum degree
    0 references
    edge-coloring
    0 references
    monochromatic cycles
    0 references

    Identifiers