Path and cycle sub-Ramsey numbers and an edge-colouring conjecture (Q1088687)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
scientific article

    Statements

    Path and cycle sub-Ramsey numbers and an edge-colouring conjecture (English)
    0 references
    0 references
    0 references
    1986
    0 references
    The sub-Ramsey number sr(G,k) of a graph G and a positive integer k is the least m such that in any edge-colouring of \(K_ m\) using k colours at most there is an isomorphic subgraph to G whose edges all have distinct colours. Theorem 1. There is a positive constant c such that if k and \(n\geq ck^ 3\) are positive integers and \(K_ n\) is coloured using no colour more than k times, then there is a Hamilton cycle whose edges all have distinct colours. This theorem implies e.g. that there exists a function \(f(k)\leq ck^ 3\) such that if \(n\geq f(k)\), then \(sr(P_ n,k)=sr(C_ n,k)=n\). \((P_ n\) is a path and \(C_ n\) a cycle both on n vertices.) It is conjecture, that the function f is linear from some \(k_ 0\) on. Theorem 2. Let \(K_{\omega}\) be edge-coloured so that each monochromatic subgraph is locally finite. Then it either contains a \(K^ 0\) (complete graph on \(\omega =\{0,1,2,...\})\) or at any vertex there begins a Hamilton path with all edges of distinct colours.
    0 references
    0 references
    Hamilton cycle
    0 references
    sub-Ramsey number
    0 references
    edge-colouring
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers