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
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
Hamilton cycle
0 references
sub-Ramsey number
0 references
edge-colouring
0 references