Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 344.05118
Autor: Chen, C.C.; Daykin, D.E.; Erdös, Paul
Title: Subgraphs with all colours in a line-coloured graph. (In English)
Source: Proc. 5th Br. comb. Conf., Aberdeen 1975, 101-112 (1976).
Review: [For the entire collection see Zbl 316.00006.]
Consider a graph G whose lines have been coloured. It is natural to look for conditions on the colouring, which ensure that a particular kind or class of coloured graphs exist as subgraphs of G. This paper deals with one such problem. Let p,q and r be positive integers with r \geq 3 and 2r \geq q \geq r. The function g(p,r,q) [resp. f(p,r,q)] is defined as the least integer \ell \geq 0 such that, whenever a graph [resp. complete grpah] on p points has each of its lines coloured with one of r-1 colours [resp. r colours] in such a way that every colour is on strictly more than \ell lines, then the graph has a polychromatic subgraph on \leq q points (polychromatic means containing all colours). Any \ell \geq \binom{p}{2}/r variously satisfies the condition for f, however, the authors prefer not to take such \ell-s into consideration, and they define f to be oo when only such values of \ell exist. In the paper a variety of results about g and f are proved, among them: g(p,3,3) = \binom{[p/2]}{2} for p \geq 1, f(p,r,2r-2) = g(p,r,2r-2) = 0 for r \geq 3, and f(p,r,2r-3) = g(p,r,2r-3) = \binom{\alpha}{2} for r \geq 4 and \alpha = [p/(r-1)]. Also some asymptotic results are obtained. Finally it is proved (for r \geq 3 and p > (1/3)r+2) that if the lines of the complete p-graph are coloured with r colours, each colour being used at least once, then there is a polychromatic trail of length \leq 2r-3 (a trail is a linesequence in which all lines are distinct). This is stronger than f(p,r,2r-2) = 0.
Reviewer: B.Toft
Classif.: * 05C15 Chromatic theory of graphs and maps
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag