A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs. (January 2014) - KITTIPASSORN, TEERADEJ; NARAYANAN, BHARGAV P.
<x content-type="archive" xml:space="preserve">Abstract</x> Given an edge colouring of a graph with a set of m colours, we say that the graph is exactly m-coloured if each of the colours is used. We consider edge colourings of the complete graph on <alternatives><inline-graphic xlink:href="ark:/27927/pgh350fdfg9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> <![CDATA[N]]> </alternatives> with infinitely many colours and show that either one can find an exactly m-coloured complete subgraph for every natural number m or there exists an infinite subset X ⊂ <alternatives><inline-graphic xlink:href="ark:/27927/pgh350fdfg9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> <![CDATA[N]]> </alternatives> coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex v in X such that X{v is 1-coloured and each edge between v and X{v has a distinct colour (all different to the colour used on X{v). This answers a question posed by Stacey and Weidl in 1999. 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.