边染色图中的2-因子

doi:10.6040/j.issn.1671-9352.0.2019.156

《山东大学学报(理学版)》 ›› 2021, Vol. 56 ›› Issue (1): 24-28.doi: 10.6040/j.issn.1671-9352.0.2019.156

• • 上一篇

边染色图中的2-因子

张爽^1,2,朱焱^1*

1.华东理工大学理学院, 上海 200237;2.珠海市第四中学, 广东珠海 519000

发布日期:2021-01-05
作者简介:张爽(1995— ), 女,硕士研究生,研究方向为图论. E-mail:18463757058@163.com *通信作者简介:朱焱(1984— ),女,博士,副教授,硕士生导师,研究方向为图论. E-mail:operationzy@163.com
基金资助:
国家自然科学基金资助项目(11671135)

2-factor of edge colored graph

ZHANG Shuang^1,2, ZHU Yan^1*

1. East China University of Science and Technology, Shanghai 200237, China;
2. Zhuhai Fourth Middle School, Zhuhai 519000, Guangdong, China

Published:2021-01-05

摘要/Abstract

摘要： 令G是含n个点的边染色图,对G中任意顶点x,定义其色邻域CN(x)为集合{c(xy)|xy∈E(G), y∈V(G)}。如果G中任意相邻的两条边都染有不同的颜色,就称G是正常染色的。证明了如果边染色图G满足对V(G)中任意两点u,v有|CN(u)∪CN(v)|≥4n/3+8,则图G含有一个正常染色2-因子。

关键词: 边染色图, 2-因子, 色邻域

Abstract: Let G be an edge colored graph. For a vertex x of G, the color neighborhood CN(x)of x is defined as the set {c(xy)|xy∈E(G), y∈V(G)}. G is properly colored if no adjacent edges have the same color. If every edge colored graph G has |CN(u)∪CN(v)|≥4n/3+8 for every pair of vertices u and v of V(G), the G contains a properly colored 2-factor.

Key words: edge colored graph, 2-factor, color neighborhood

中图分类号:

O157.5

张爽,朱焱. 边染色图中的2-因子[J]. 《山东大学学报(理学版)》, 2021, 56(1): 24-28.

ZHANG Shuang, ZHU Yan. 2-factor of edge colored graph[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(1): 24-28.

参考文献

[1] CHOUDUM S A, PAULRAJ M S. Regular factors in K_1,3-free graphs[J]. Journal of Graph Theory, 1991, 15(3):259-265.
[2] BRANDT S, CHEN G T, FAUDREE R, et al. Degree conditions for 2-factors[J]. Journal of Graph Theory, 1997, 24(2): 165-173.
[3] HAGGKVIST R, A talk at intern. colloquium on combinatorics and graph theory at Balatonlelle[R]. Hungary, July 15-19,1996.
[4] 丁录顺,王光辉,颜谨.不含三角形图的正常染色路和正常染色圈[J]. 运筹学学报, 2014, 18(3):116-120. DING Lushun, WANG Guanghui, YAN Jin. The properly colored paths and cycles for the triangle-free graphs[J]. Operations Research Transactions, 2014, 18(3):116-120.
[5] LO A. An edge-colored version of Diracs theorem[J]. SIAM Journal on Discrete Mathematics, 2014, 28(1):18-36.
[6] JACKSON B, YOSHIMOTO K. Even subgraphs of bridgeless graphs and 2-factors of line graphs[J]. Discrete Mathematics, 2007, 307(22):2775-2785.
[7] GOULD R J, HYNDS E. A note on cycles in 2-factors of line graphs[J]. Bulletin of ICA, 1999(26):46-48.
[8] FAUDREE R, FAVARON O, FLANDRIN E, et al. On 2-factors in claw-free graphs[J]. Discrete Mathematics, 1999, 206(1/2/3):131-137.
[9] FAUDREE J R, FAUDREE R J, RYJÁCEK Z. Forbidden subgraphs that imply 2-factors[J]. Discrete Mathematics, 2008, 308(9):1571-1582.
[10] PETERSEN J. Die Theorie der regulären graphs[J]. Acta Mathematica, 1891, 15:193-220.
[11] NISHIMURA T. Regular factors of line graphs[J]. Discrete Mathematics, 1990, 85(2):215-219.
[12] NISHIMURA T. Component factors and induced subgraphs[J]. Journal of Graph Theory, 1996, 22(4):305-308.
[13] NISHIMURA T. A degree condition for the existence of k-factors[J]. Journal of Graph Theory, 1992, 16(2):141-151.
[14] KUNDU S. The k-factor conjecture is true[J]. Discrete Mathematics, 1973, 6(4):367-376.
[15] KATERINIS P. Some results on the existence of 2n-factors in terms of vertex deleted subgraphs[J]. Ars Combin, 1983, 16(B):271-277.
[16] IIDA T, NISHIMURA T. Neighborhood conditions and k-factors[J]. Tokyo Journal of Mathematics, 1997, 20(2):411-418.
[17] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan Education UK, 1976.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

边染色图中的2-因子

2-factor of edge colored graph

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

多维度评价

本文评价

推荐阅读 0

[1]	宋宝阳,王晓宗,任宇屏. 边染色图中的正常染色的路和圈[J]. J4, 2012, 47(6): 63-66.
[2]	徐进1,王光雷2. 边染色图中的长彩色路问题[J]. J4, 2010, 45(12): 22-23.
[3]	李硕,李峰,梁峰 . 边染色图中的彩色围长[J]. J4, 2008, 43(6): 19-20 .
[4]	高云澍,李国君 . 二分图中含有大圈的2-因子[J]. J4, 2007, 42(4): 28-31 .