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

doi:10.3969/j.issn.0253-2778.2020.03.012

Journal of University of Science and Technology of China ›› 2020, Vol. 50 ›› Issue (3): 343-348.DOI: 10.3969/j.issn.0253-2778.2020.03.012

• Original Paper • Previous Articles Next Articles

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

YUAN Longtu

Received:2020-02-28 Revised:2020-03-28 Accepted:2020-03-28 Online:2020-03-31 Published:2020-03-28
About author:YUAN Longtu, male, born in 1984, PhD. Research field: Extremum graph theory. E-mail: vicky576@mail.ustc.edu.cn
Supported by:
Supported by the National Natural Science Foundation of National Natural Science Foundation(11901554).

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.

Key words: edge coloring, monochromatic copy, matching critical graph

CLC Number:

O157.4

[1]	. Protective effect of Fe3O4 nanoparticles on cadmium chloride-induced toxicity in the small intestine of mice [J]. Journal of University of Science and Technology of China, 2020, 50(7): 887-893.
[2]	. Ore-type condition for loose Hamilton cycles in 3-uniform hypergraphs [J]. Journal of University of Science and Technology of China, 2020, 50(5): 669-672.
[3]	. On the multiplicatively weighted Harary index of composite graphs [J]. Journal of University of Science and Technology of China, 2020, 50(3): 261-270.
[4]	. LMD-BPF method for modal parameter identification and its applications [J]. Journal of University of Science and Technology of China, 2020, 50(3): 271-281.
[5]	. The Erdo″s-So′s conjecture for 2-center spiders [J]. Journal of University of Science and Technology of China, 2020, 50(3): 289-293.
[6]	. L2-harmonic p-forms on submanifolds with finite total curvature [J]. Journal of University of Science and Technology of China, 2020, 50(3): 294-299.
[7]	. Biharmonic submanifolds with mean parallel curvature on Mm(c)×R [J]. Journal of University of Science and Technology of China, 2020, 50(3): 312-316.
[8]	. A note on the maximal degree in random k-trees [J]. Journal of University of Science and Technology of China, 2020, 50(3): 328-334.
[9]	. Dual-band filter design based on composite patch and substrate integrated waveguide structures [J]. Journal of University of Science and Technology of China, 2020, 50(3): 363-368.
[10]	HU Wanbao, HU Shuai, CHEN Wenwen, CUI Liangwu. Repairing multiple failures for algebraic geometry codes [J]. Journal of University of Science and Technology of China, 2020, 50(2): 140-145.
[11]	WEN Zebo, KANG Yu, CAO Yang, WEI Meng, SONG Weiguo. Features selection for video smoke detection using random forest [J]. Journal of University of Science and Technology of China, 2017, 47(8): 653-664.
[12]	XU Ziwei, WANG Peng, CHEN Zonghai. A two-stage feature selection method based on Fisher’s ratio and prediction risk for telecom customer churn prediction [J]. Journal of University of Science and Technology of China, 2017, 47(8): 686-694.
[13]	QIAN Liqin , SHI Minjia, SOK Lin, PING Jingshui. Quadratic residue codes over Fp+u Fp+ v Fp+uv Fp+v2 Fp+uv2 Fp [J]. Journal of University of Science and Technology of China, 2017, 47(7): 602-609.
[14]	SU Hetang, ZHAO Yuxia, DING Jian, DONG Kexiu, YU Wenjuan, HE Ye. Simultaneous improvement of Jsc, Voc and FF of polymer solar cells with CuI as hole transport layer [J]. Journal of University of Science and Technology of China, 2017, 47(7): 621-626.

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

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics

Comments