# Fete of Combinatorics and Computer ScienceExtremal Graphs and Multigraphs with Two Weighted Colours

Fete of Combinatorics and Computer Science: Extremal Graphs and Multigraphs with Two Weighted... [We study the extremal properties of coloured multigraphs H, whose edge set is the union of two simple graphs Hr and Hb (thought of as red and blue edges) on the same vertex set. Let 0 ≤ p ≤ 1 and let q = 1 - p. The extremal problem considered here, for a given fixed H, is to find the maximum weight p|E(Gr)|+q|E(Gb)| of large coloured multigraphs G that do not contain if as a subgraph. In fact, motivated by applications (typically to the study of hereditary properties by means of Szemerédi’s Lemma), we consider the maximum restricted to those G whose underlying graph is complete — that is, every pair of vertices is joined by at least one edge.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

# Fete of Combinatorics and Computer ScienceExtremal Graphs and Multigraphs with Two Weighted Colours

Part of the Bolyai Society Mathematical Studies Book Series (volume 20)
Editors: Katona, Gyula O. H.; Schrijver, Alexander; Szőnyi, Tamás; Sági, Gábor
47 pages      /lp/springer-journals/fete-of-combinatorics-and-computer-science-extremal-graphs-and-XvyIEaPQMj
Publisher
Springer Berlin Heidelberg
© János Bolyai Mathematical Society and Springer-Verlag 2010
ISBN
978-3-642-13579-8
Pages
239 –286
DOI
10.1007/978-3-642-13580-4_10
Publisher site
See Chapter on Publisher Site

### Abstract

[We study the extremal properties of coloured multigraphs H, whose edge set is the union of two simple graphs Hr and Hb (thought of as red and blue edges) on the same vertex set. Let 0 ≤ p ≤ 1 and let q = 1 - p. The extremal problem considered here, for a given fixed H, is to find the maximum weight p|E(Gr)|+q|E(Gb)| of large coloured multigraphs G that do not contain if as a subgraph. In fact, motivated by applications (typically to the study of hereditary properties by means of Szemerédi’s Lemma), we consider the maximum restricted to those G whose underlying graph is complete — that is, every pair of vertices is joined by at least one edge.]

Published: Jan 31, 2011

Keywords: Edit Distance; Extremal Function; Graph Sequence; Extremal Graph; Blue Edge