未被某个匹配临界图的所有单色复制覆盖的边数

doi:10.3969/j.issn.0253-2778.2020.03.012

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (3): 343-348.DOI: 10.3969/j.issn.0253-2778.2020.03.012

未被某个匹配临界图的所有单色复制覆盖的边数

袁龙图

华东师范大学数学科学学院，上海 200241

收稿日期:2020-02-28 修回日期:2020-03-28 接受日期:2020-03-28 出版日期:2020-03-31 发布日期:2020-03-28

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

摘要： 给定一个图H，另f(n,H)为完全图Kn的所有二色边染色中，包含未被单色图H的复制覆盖的边数的最大值.图的图兰数，记作ex(n,H)，是指所有的n个顶点的图中，不含有H作为子图的图的所含有边数的最大值.显然对于任意的n和H，f(n,H)大于等于ex(n,H).我们证明了，对于匹配临界图，以上两个数值当n是充分大的时候是相等的.

关键词: 边染色, 单色复制, 匹配临界图

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

中图分类号:

O157.4

袁龙图. 未被某个匹配临界图的所有单色复制覆盖的边数[J]. 中国科学技术大学学报, 2020, 50(3): 343-348.

[1]	王晓琴，张燕，谭伟航，聂楷，徐小龙. 纳米四氧化三铁对氯化镉诱导小鼠小肠毒性的保护作用[J]. 中国科学技术大学学报, 2020, 50(7): 887-893.
[2]	余磊. 3一致超图中线性哈密顿圈的Ore条件[J]. 中国科学技术大学学报, 2020, 50(5): 669-672.
[3]	田静，彭贵琴，裴利丹，潘向峰. 复合图的乘权Harary指数[J]. 中国科学技术大学学报, 2020, 50(3): 261-270.
[4]	边杰，郑锦妮，陈亚农，徐友良，陈运西. 模态参数识别的LMD-BPF方法及其应用[J]. 中国科学技术大学学报, 2020, 50(3): 271-281.
[5]	王仕成，侯新民. 关于2-中心蜘蛛树的Erdo″s-So′s猜想[J]. 中国科学技术大学学报, 2020, 50(3): 289-293.
[6]	周俊东，尹松庭. 具有有限总曲率子流形的L2调和p形式[J]. 中国科学技术大学学报, 2020, 50(3): 294-299.
[7]	米蓉. Mm(c)×R中具有平行平均曲率的2-调和子流形[J]. 中国科学技术大学学报, 2020, 50(3): 312-316.
[8]	冯群强，邹纯，李兴. 随机k-树的最大度数[J]. 中国科学技术大学学报, 2020, 50(3): 328-334.
[9]	李安然. 基于复合贴片CSIW结构的双带滤波器设计[J]. 中国科学技术大学学报, 2020, 50(3): 363-368.
[10]	胡万宝，胡帅，陈雯雯，崔良武. 多节点修复的代数几何码[J]. 中国科学技术大学学报, 2020, 50(2): 140-145.
[11]	文泽波，康宇，曹洋，魏梦，宋卫国. 基于随机森林特征选择的视频烟雾检测[J]. 中国科学技术大学学报, 2017, 47(8): 653-664.
[12]	徐子伟，王鹏，陈宗海. 一种基于Fisher比率和预测风险准则的电信客户流失预测分步特征选择方法[J]. 中国科学技术大学学报, 2017, 47(8): 686-694.
[13]	钱丽琴，施敏加，SOKLin，平静水. 环 Fp+u Fp+v Fp+uv Fp+v2 Fp+uv2 Fp 上的二次剩余码[J]. 中国科学技术大学学报, 2017, 47(7): 602-609.
[14]	苏和堂，赵玉霞，丁健，董可秀，于文娟，何烨. CuI空穴传输层提高聚合物太阳能电池Jsc, Voc及FF的研究[J]. 中国科学技术大学学报, 2017, 47(7): 621-626.

未被某个匹配临界图的所有单色复制覆盖的边数

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

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价