TY - JOUR
T1 - On the number of edges not covered by monodiromatic copies of a matching-critical graph
AU - Yuan, Longtu
N1 - Publisher Copyright:
© 2020, Editorial Department of Journal of University of Science and Technology of China. All rights reserved.
PY - 2020/3
Y1 - 2020/3
N2 - Given a graph H, let ƒ(n,H) denote the maximum number of edges not contained in any monochromatic copy of H ina 2-edge-coloring of Kn. The Turan 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.
AB - Given a graph H, let ƒ(n,H) denote the maximum number of edges not contained in any monochromatic copy of H ina 2-edge-coloring of Kn. The Turan 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.
KW - Edge coloring
KW - Matching critical graph
KW - Monochromatic copy
UR - https://www.scopus.com/pages/publications/85104828553
U2 - 10.3969/j.issn.0253-2778.2020.03.012
DO - 10.3969/j.issn.0253-2778.2020.03.012
M3 - 文章
AN - SCOPUS:85104828553
SN - 0253-2778
VL - 50
SP - 343
EP - 348
JO - Journal of University of Science and Technology of China
JF - Journal of University of Science and Technology of China
IS - 3
M1 - 0253-2778(2020)03-0343-06
ER -