Multicolour Turán problems
type: Item
instance of: scholarly article
title: Multicolour Turán problems
zbMATH Open document ID: 1056.05080
published in: Advances in Applied Mathematics
publication date: 2004-10-12T00:00:00Z
review text: A colouring of a multigraph \(G\) with \(k\) colours is a decomposition of its egde multiset into \(k\) colour classes. A submultigraph \(H\) of \(G\) is called multicoloured or rainbow if its edges all have distinct colours. The parameter \(\text{ex}_k(n,H)\) is defined as the maximum number of edges in a multigraph of order \(n\), that has a \(k\)-colouring not containing a multicoloured copy of \(H\). This parameter provides a generalisation of the Turán number \(\text{ex}(n,H)\) that denotes the maximum number of edges in a graph on \(n\) vertices not containing a copy of \(H\). Some relationships of \(\text{ex}_k(n,H)\) and \(\text{ex}(n,H)\) are presented. The exact values of the investigated parameter are obtained for sufficiently large complete graphs, 3-colour-critical graphs, some bipartite graphs (particularly for \(C_4\)).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2107226
zbMATH Keywords: rainbow colouring
zbMATH Keywords: extremal problems
author: Peter Keevash
author: Michael Saks
author: Benny Sudakov
author: J. Verstraëte
reviewed by: Gabriel Semanišin
MaRDI profile type: Publication
full work available at URL: j.aam.2003.08.005
OpenAlex ID: W2117407892
cites work: Norm-graphs: Variations and applications
cites work: Q4398864
cites work: Graphs without quadrilaterals
cites work: On the number of edges of quadrilateral-free graphs
cites work: An Upper Bound on Zarankiewicz' Problem
cites work: Turán problems for integer-weighted graphs
cites work: Norm-graphs and bipartite Turán numbers
cites work: On a problem of K. Zarankiewicz
cites work: Q5548826
cites work: On the theory of graphs
DOI: 10.1016/J.AAM.2003.08.005
description: scientific article; zbMATH DE number 2107226