Premium
Essentially Infinite Colourings of Graphs
Author(s) -
Bollobás B.,
Kohayakawa Y.,
Schelp R. H.
Publication year - 2000
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610700008796
Subject(s) - combinatorics , bipartite graph , mathematics , ramsey's theorem , graph , discrete mathematics , integer (computer science) , enhanced data rates for gsm evolution , computer science , telecommunications , programming language
The classical canonical Ramsey theorem of Erdős and Rado states that, for any integer q ⩾ 1, any edge colouring of a large enough complete graph contains one of three canonically coloured complete subgraphs of order q . Of these canonical subgraphs, one is coloured monochromatically while each of the other two has its edge set coloured with many different colours. The paper presents a condition on colourings that, roughly speaking, requires them to make effective use of many colours (‘essential infiniteness’); this condition is then shown to imply that the colourings in question must contain large refinements of one of two ‘unavoidable’ colourings that are rich in colours. As it turns out, one of these unavoidable colourings is one of the canonical colourings of Erdős and Rado, and the other is a ‘bipartite variant’ of this colouring.