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

Cite this: JUSTC, 2020, 50(3): 343-348
https://doi.org/10.3969/j.issn.0253-2778.2020.03.012
Funds: Supported by the National Natural Science Foundation of National Natural Science Foundation(11901554).
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: February 27, 2020
  • Revised Date: March 27, 2020
  • Accepted Date: March 27, 2020
  • Published Date: March 30, 2020
    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)
    References (7)
    Related Articles
    Track Citations

Catalog

    Get Citation
    {{if article.pdfAccess}}
    {{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF
    {{/if}}
    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.

    Related Articles

    [1]Yun Cai, Shuguang Zhang. Optimal matching for heterogeneous treatment effect estimation[J]. JUSTC, 2023, 53(7): 0707. DOI: 10.52396/JUSTC-2023-0033
    [2]LI Xintian, LIU Shiping. Lin-Lu-Yau curvature and diameter of amply regular graphs[J]. JUSTC, 2021, 51(12): 889-893. DOI: 10.52396/JUST-2021-0232
    [3]CAI Gaixiang, MEI Peilin, YU Guidong. Inverse degree and properties of graphs[J]. JUSTC, 2020, 50(6): 852-859. DOI: 10.3969/j.issn.0253-2778.2020.06.019
    [4]TIAN Jing, PENG Guiqin, PEI Lidan, PAN Xiangfeng. On the multiplicatively weighted Harary index of composite graphs[J]. JUSTC, 2020, 50(3): 261-270. DOI: 10.3969/j.issn.0253-2778.2020.03.002
    [5]FU Shunan, LIAO Hongyi, NIE Jiaxin. A multi-stage infectious disease model on the complete graph[J]. JUSTC, 2020, 50(2): 132-139. DOI: 10.3969/j.issn.0253-2778.2020.02.008
    [6]QIAO Zhi, PAN Yongliang. A note on optimistic strongly regular graphs[J]. JUSTC, 2017, 47(3): 197-203. DOI: 10.3969/j.issn.0253-2778.2017.03.001
    [7]HU Baoli, YOU Jinguo, ZHOU Cuilian, WANG Yang, CUI Hongbo. An efficient weighted graph aggregation algorithm[J]. JUSTC, 2016, 46(3): 180-187. DOI: 10.3969/j.issn.0253-2778.2016.03.002
    [8]CAI Hongjian. Invariant graphs of rational maps[J]. JUSTC, 2015, 45(3): 173-185. DOI: 10.3969/j.issn.0253-2778.2015.03.001
    [9]HONG Zhenmu, XU Junming. Edge fault-tolerance of super restricted edge-connected Cartesian product graphs[J]. JUSTC, 2014, 44(12): 967-974. DOI: 10.3969/j.issn.0253-2778.2014.12.001
    [10]LI Xiaoxin, ZHA Shuping, FAN Yizheng. An upper bound for the Harary index of a connected graph and the corresponding extremal graph[J]. JUSTC, 2014, 44(2): 96-100. DOI: 10.3969/j.issn.0253-2778.2014.02.003
    TrendMD
    2020 No. 3 Volume 50 Issue 3 PP. 343-348
    Cover

    Article Metrics

    Article views (137) PDF downloads (213)

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

    Supported by: Beijing Renhe Information Technology Co., Ltd.  Baidu Analytics

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return