Loading...
Please wait, while we are loading the content...
Similar Documents
A Canonical Ramsey Theorem for Exactly m-Coloured Complete Subgraphs
| Content Provider | Scilit |
|---|---|
| Author | Kittipassorn, Teeradej Narayanan, Bhargav P. |
| Copyright Year | 2013 |
| Description | 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 $\mathbb{N}$ 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 ⊂ $\mathbb{N}$ 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. |
| Related Links | http://arxiv.org/pdf/1303.2997 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/4DF63AFA8956B789414C8B1A86831E56/S0963548313000503a.pdf/div-class-title-a-canonical-ramsey-theorem-for-exactly-span-class-italic-m-span-coloured-complete-subgraphs-div.pdf |
| Ending Page | 115 |
| Page Count | 14 |
| Starting Page | 102 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548313000503 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 1 |
| Volume Number | 23 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2014-01-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Primary 05c55 Secondary 05c63 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
