ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

Funds:  Supported by the National Natural Science Foundation of National Natural Science Foundation(11901554).
Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2020.03.012
More Information
  • Author Bio:

    YUAN Longtu, male, born in 1984, PhD. Research field: Extremum graph theory. E-mail: vicky576@mail.ustc.edu.cn

  • Received Date: 28 February 2020
  • Accepted Date: 28 March 2020
  • Rev Recd Date: 28 March 2020
  • Publish Date: 31 March 2020
    Abstract

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

    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.
    • FullText(HTML)
  • loading
    • References(7)
  • [1]
    KEEVASH P, SUDAKOV B. On the number of edges not covered by monochromatic copies of axed graphs[J]. J. Combin. Theory Ser. B, 2004,108: 41-53.
    [2]
    MA J. On edges not in monochromatic copies of axed bipartite graph[J]. J. Combin. Theory Ser. B, 2017, 123: 240-248.
    [3]
    LIU H, PIKHURKOO, SHARIFZADEH M. Edges not in any monochromatic copy of axed graph[J]. J. Combin. Theory Ser. B, 2019, 135: 16-43.
    [4]
    SIMONOVITS M. How to solve a Turan type extremal graph problem? (linear decomposition), Contemporary trends in dicrete mathematics[J]. Discrete Math. Theoret. Comput. Sci., 1997, 49: 283-305.
    [5]
    SIMONOVITS M. Extremal graph problems with symmetrical extremal graphs, additionnal chromatic conditions[J]. Discrete Mathematics, 1974, 7: 349-376.
    [6]
    ERDS K, STONE A H. On the structure of linear graphs[J]. Bull. Amer. Math. Soc. 1946, 52: 1087-1091.
    [7]
    SIMONOVITS M. A method for solving extremal problems in graph theory, stability problems[C]// Proc. Colloq., Tihany,Theory of Graphs.1968: 279-319.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    KEEVASH P, SUDAKOV B. On the number of edges not covered by monochromatic copies of axed graphs[J]. J. Combin. Theory Ser. B, 2004,108: 41-53.
    [2]
    MA J. On edges not in monochromatic copies of axed bipartite graph[J]. J. Combin. Theory Ser. B, 2017, 123: 240-248.
    [3]
    LIU H, PIKHURKOO, SHARIFZADEH M. Edges not in any monochromatic copy of axed graph[J]. J. Combin. Theory Ser. B, 2019, 135: 16-43.
    [4]
    SIMONOVITS M. How to solve a Turan type extremal graph problem? (linear decomposition), Contemporary trends in dicrete mathematics[J]. Discrete Math. Theoret. Comput. Sci., 1997, 49: 283-305.
    [5]
    SIMONOVITS M. Extremal graph problems with symmetrical extremal graphs, additionnal chromatic conditions[J]. Discrete Mathematics, 1974, 7: 349-376.
    [6]
    ERDS K, STONE A H. On the structure of linear graphs[J]. Bull. Amer. Math. Soc. 1946, 52: 1087-1091.
    [7]
    SIMONOVITS M. A method for solving extremal problems in graph theory, stability problems[C]// Proc. Colloq., Tihany,Theory of Graphs.1968: 279-319.
    Recommended articles
    TrendMD
    Volume 50 Issue 3 page: 343-348
    Cover

    Article Metrics

    Article views (59) PDF downloads(76)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return