Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

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
Marchant, Edward; Thomason, Andrew
Fete of Combinatorics and Computer Science — Jan 31, 2011
Download PDF
47 pages

Loading next page...
 
/lp/springer-journals/fete-of-combinatorics-and-computer-science-extremal-graphs-and-XvyIEaPQMj
Publisher
Springer Berlin Heidelberg
Copyright
© 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

There are no references for this article.