JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2021, Vol. 56 ›› Issue (1): 24-28.doi: 10.6040/j.issn.1671-9352.0.2019.156

Previous Articles    

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

PDF (PC)

647

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

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   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd