24
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Given a colouring of the edges of a graph, we say that the graph is exactly m-coloured if the number of distinct colours used by the colouring is m. The question of finding exactly m-coloured complete subgraphs was first considered by Erickson in 1994; Stacey and Weidl, in 1999, partially settled a conjecture made by Erickson and considered several related problems. The primary aim of this paper is to answer a question posed by Stacey and Weidl. We consider edge colourings of the complete graph on the natural numbers with infinitely many colours, and study under which circumstances we can find exactly m-coloured complete subgraphs for every natural number m. We prove that if, for some natural number m, one cannot find an exactly m-coloured complete subgraph, then the colouring must admit a complete infinite subgraph which is coloured in one of exactly two specific ways. The techniques that we develop also enable us to resolve some further questions about finding exactly m-coloured complete subgraphs in colourings with finitely many colours.

          Related collections

          Author and article information

          Journal
          1303.2997

          Combinatorics
          Combinatorics

          Comments

          Comment on this article