Extremal Graphs and Multigraphs with Two Weighted Colours
Extremal Graphs and Multigraphs with Two Weighted Colours
复制标题
具有两种加权颜色的极值图和多重图
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Thomason
中科院分区：
文献类型：
--
作者：
E. Marchant;A. Thomason
本文研究了着色重图H的极值性质，其边集是两个简单图Hr和H B（被认为是红边和蓝边）在同一顶点集上的并.设0 ≤ p ≤ 1，q = 1 -p，对给定的H，求极值问题是求最大权p| E（G r）|+Q| E（G B）|不包含if作为子图的大型着色重图G的一个例子。事实上，出于应用的动机（通常是通过Szemeredi引理来研究遗传性质），我们认为最大值仅限于那些G的基础图是完整的-也就是说，每对顶点至少有一条边连接。
We study the extremal properties of coloured multigraphs H, whose edge set is the union of two simple graphs H r and H b (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(G r )|+q|E(G b )| 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 Szemeredi’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.