ISSN 0253-2778

CN 34-1054/N

open

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

  • 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.
  • loading

Catalog

    {{if article.pdfAccess}}
    {{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF
    {{/if}}
    XML

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return