A canonical ramsey theorem for exactly m-coloured complete subgraphs

Teeradej Kittipassorn, Bhargav P. Narayanan

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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 ℕ 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 ⊂ ℕ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex ν in X such that X\{ν} is 1-coloured and each edge between ν and X\{ν} has a distinct colour (all different to the colour used on X\{ν}). 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.

Original languageEnglish (US)
Pages (from-to)102-115
Number of pages14
JournalCombinatorics Probability and Computing
Volume23
Issue number1
DOIs
StatePublished - Jan 1 2014

Fingerprint

Ramsey's Theorem
Subgraph
Color
Coloring
Edge Coloring
Graph in graph theory
Natural number
Injective
Complete Graph
Colouring
Resolve
Distinct
Subset
Vertex of a graph

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this

@article{19c80c2ecc1541f9abe142654e8c38d8,
title = "A canonical ramsey theorem for exactly m-coloured complete subgraphs",
abstract = "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 ℕ 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 ⊂ ℕ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex ν in X such that X\{ν} is 1-coloured and each edge between ν and X\{ν} has a distinct colour (all different to the colour used on X\{ν}). 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.",
author = "Teeradej Kittipassorn and Narayanan, {Bhargav P.}",
year = "2014",
month = "1",
day = "1",
doi = "10.1017/S0963548313000503",
language = "English (US)",
volume = "23",
pages = "102--115",
journal = "Combinatorics Probability and Computing",
issn = "0963-5483",
publisher = "Cambridge University Press",
number = "1",

}

A canonical ramsey theorem for exactly m-coloured complete subgraphs. / Kittipassorn, Teeradej; Narayanan, Bhargav P.

In: Combinatorics Probability and Computing, Vol. 23, No. 1, 01.01.2014, p. 102-115.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A canonical ramsey theorem for exactly m-coloured complete subgraphs

AU - Kittipassorn, Teeradej

AU - Narayanan, Bhargav P.

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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 ℕ 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 ⊂ ℕ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex ν in X such that X\{ν} is 1-coloured and each edge between ν and X\{ν} has a distinct colour (all different to the colour used on X\{ν}). 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.

AB - 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 ℕ 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 ⊂ ℕ coloured in one of two canonical ways: either the colouring is injective on X or there exists a distinguished vertex ν in X such that X\{ν} is 1-coloured and each edge between ν and X\{ν} has a distinct colour (all different to the colour used on X\{ν}). 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.

UR - http://www.scopus.com/inward/record.url?scp=84889635118&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84889635118&partnerID=8YFLogxK

U2 - 10.1017/S0963548313000503

DO - 10.1017/S0963548313000503

M3 - Article

AN - SCOPUS:84889635118

VL - 23

SP - 102

EP - 115

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

SN - 0963-5483

IS - 1

ER -