未被某个匹配临界图的所有单色复制覆盖的边数

On the number of edges not covered by monochromatic copies of a matching-critical graph

摘要: 给定一个图H，另f(n,H)为完全图Kn的所有二色边染色中，包含未被单色图H的复制覆盖的边数的最大值.图的图兰数，记作ex(n,H)，是指所有的n个顶点的图中，不含有H作为子图的图的所含有边数的最大值.显然对于任意的n和H，f(n,H)大于等于ex(n,H).我们证明了，对于匹配临界图，以上两个数值当n是充分大的时候是相等的.

Abstract: Given a graph H, let f(n,H) denote the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of Kn. The Turn number of a graph H, denoted by ex(n,H), is the maximum number of edges in an n-vertex graph which does not contain H as a subgraph. It is easy to see that f(n,H)≥ex(n,H) for any H and n. We show that this lower bound is tight for matching-critical graphs including Pertersen graph and vertex-disjoint union of copies of cliques with same order.