反d-退化图中的点不交3-圈

doi:10.6040/j.issn.1671-9352.0.2019.089

《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (9): 51-53.doi: 10.6040/j.issn.1671-9352.0.2019.089

• • 上一篇

反d-退化图中的点不交3-圈

牛蓓^*,张欣

西安电子科技大学数学与统计学院, 陕西西安 710071

发布日期:2020-09-17
作者简介:牛蓓(1993— ),女,博士研究生,研究方向为图论及其应用. E-mail:beiniu@stu.xidian.edu.cn*通信作者
基金资助:
西安市科协青年人才托举计划项目(2018-6);国家自然科学基金资助项目(11871055);陕西省自然科学基础研究计划面上基金项目)2017JM1010)

Vertex-disjoint triangles in anti-d-degenerate graphs

NIU Bei^*, ZHANG Xin

School of Mathematics and Statistics, Xidian University, Xian 710071, Shaanxi, China

Published:2020-09-17

摘要/Abstract

摘要： 如果图G的补图(-overG)是d-退化图,则称图G是反d-退化图。证明了当|G|=3k且δ(G)≥k≥26d时,反d-退化图G包含k个点不交的3-圈,其中d≥2。

关键词: (反)d-退化图, 独立集, 点不交3-圈, 均匀染色

Abstract: A graph G is an anti-d-degenerate graph if its complement graph (-overG) is a d-degenerate graph. It is proved that every anti-d-degenerate graph G with |G|=3k and δ(G)≥k≥26d contains k vertex-disjoint triangles, where d≥2.

Key words: (anti)-d-degenerate graph, independent set, vertex-disjoint triangle, equitable coloring

中图分类号:

O157.5

牛蓓,张欣. 反d-退化图中的点不交3-圈[J]. 《山东大学学报(理学版)》, 2020, 55(9): 51-53.

NIU Bei, ZHANG Xin. Vertex-disjoint triangles in anti-d-degenerate graphs[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2020, 55(9): 51-53.

参考文献

[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan Education UK, 1976.
[2] CORRÁDI K, HAJNAL A. On the maximal number of independent circuits in a graph[J]. Acta Mathematica Academiae Scientiarum Hungaricae, 1963, 14(3/4):423-439.
[3] ERDÖS P. Theory of graphs and its Applications[M]. Prague: Czech Acad Sci Pub, 1964: 159.
[4] HAJNAL A, SZEMERÉDI E. Proof of a conjecture of P. Erdös[J]. Combinatorial Theory and Its Application, 1970, 2:601-623.
[5] KIERSTEAD H A, KOSTOCHKA A V. Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture[J]. Combinatorica, 2010, 30(2):201-216
[6] KIERSTEAD H A, KOSTOCHKA A V. Ore-type versions of Brooks' theorem[J]. Journal of Combinatorial Theory, Series B, 2009, 99(2):298-305.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

反d-退化图中的点不交3-圈

Vertex-disjoint triangles in anti-d-degenerate graphs

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

多维度评价

本文评价

推荐阅读 0

[1]	伍芳兰1，左连翠2*. 一类特殊笛卡尔积图的均匀染色[J]. J4, 2013, 48(4): 20-24.
[2]	刘树利. 森林的非正常均匀染色[J]. J4, 2010, 45(8): 40-42.