### 2-factor of edge colored graph

ZHANG Shuang1,2, ZHU Yan1*

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: 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.

CLC Number:

• O157.5
 [1] CHOUDUM S A, PAULRAJ M S. Regular factors in K1,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.
 [1] SONG Bao-yang, WANG Xiao-zong, REN Yu-ping. Properly colored paths and cycles in edge colored graphs [J]. J4, 2012, 47(6): 63-66. [2] GAO Yun-shu and LI Guo-jun . On 2-factors with large cycles in biparitite graph [J]. J4, 2007, 42(4): 28-31 .
Viewed
Full text

Abstract

Cited

Shared
Discussed