Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

In this paper, we survey results and conjectures on degree conditions for the existence of vertex-disjoint cycles and paths. In particular, we focus on the type of degree conditions, the type of cycles or paths, and relations between results or conjectures.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Abbasi, S.: Ph.D Thesis (Rutgers University 1998)

  2. Aigner, M., Brandt, S.: Embedding arbitrary graphs of maximum degree two. J. Lond. Math. Soc. 48, 39–51 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ainouche, A., Christofides, N.: Condition for the existence of hamiltonian circuits in graphs based on vertex degrees. J. Lond. Math. Soc. 32, 385–391 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  4. Ali, A.A., Staton, W.: The extremal question for cycles with chords. Ars Comb. 51, 193–197 (1999)

    MathSciNet  MATH  Google Scholar 

  5. Alon, N.: Disjoint directed cycles. J. Comb. Theory Ser. B 68, 167–178 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  6. Alon, N., Fischer, E.: 2-factors in dense graphs. Discret. Math. 152, 13–23 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  7. Alon, N., Yuster, R.: \(H\)-factors in dense graphs. J. Comb. Theory Ser. B 66, 269–282 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  8. Amar, D.: Partition of a bipartite hamiltonian graph into two cycles. Discrete Math. 58, 1–10 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  9. Amar, D., Flandrin, E., Gancarzewicz, G.: Cyclability in bipartite graphs. Opusc. Math. 29, 345–364 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Andreae, T.: On independent cycles and edges in graphs. Discrete Math. 149, 291–297 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  11. Babu, ChS, Diwan, A.A.: Disjoint cycles with chords in graphs. J. Graph Theory 60, 87–98 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. Balister, P., Li, H., Schelp, R.: Decompositions of graphs into cycles with chords. J. Combin. Theory Ser. B 128, 47–65 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  13. Ban, A.: Decomposing weighted graphs. J. Graph Theory 86, 250–254 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bauer, R., Wang, H.: Disjoint triangles and pentagons in a graph. Australas. J. Comb. 46, 79–89 (2010)

    MathSciNet  MATH  Google Scholar 

  15. Bazgan, C., Tuza, Z., Vanderpooten, D.: Efficient algorithms for decomposing graphs under degree constraints. Discrete Appl. Math. 155, 979–988 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bekkai, S., Kouider, M.: On pseudo 2-factors. Discrete Appl. Math. 157, 774–779 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Berman, K.E.: Proof of a conjecture of Häggkvist on cycles and independent edges. Discrete Math. 46, 9–13 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  18. Bermond, J.C.: On hamiltonian walks. Congr. Numer. 15, 41–51 (1976)

    MathSciNet  MATH  Google Scholar 

  19. Bermond, J.C., Thomassen, C.: Cycles in digraphs-a survey. J. Graph Theory 5, 1–43 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  20. Bialostocki, A., Finkel, D., Gyárfás, A.: Disjoint chorded cycles in graphs. Discrete Math. 308, 5886–5890 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Birmelé, E., Bondy, J.A., Reed, B.A.: The Erdős-Pósa property for long circuits. Combinatorica 27, 135–145 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  22. Bollobás, B., Brightwell, C.: Cycles through specified vertices. Combinatorica 13, 147–155 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  23. Bollobás, B., Eldridge, S.E.: Packings of graphs and applications to computational complexity. J. Comb. Theory Ser. B 25, 105–124 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  24. Bollabás, B., Scott, A.D.: Problems and results on judicious partitions. Random Struct. Algorithms 21, 414–430 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Bondy, J.A.: A remark on two sufficient conditions for Hamilton cycles. Discrete Math. 22, 191–193 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  26. Bondy, J.A.: Longest paths and cycles in graphs of high degree, Research Report CORR 80–16, University of Waterloo, Waterloo, Ont., (1980)

  27. Brandt, S., Chen, G., Faudree, R.J., Gould, R.J., Lesniak, L.: Degree conditions for 2-factors. J. Graph Theory 24, 165–173 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  28. Broersma, H., Tuinstra, H.: Independence trees and Hamilton cycles. J. Graph Theory 29, 227–237 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  29. Bruhn, H., Joos, F., Schaudt, O.: Long cycles through prescribed vertices have the Erdős-Pósa property, arXiv:1412.2894

  30. Bush, A., Zhao, Y.: Minimum degree thresholds for bipartite graph tiling. J. Graph Theory 70, 92–120 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  31. Catlin, P.A.: Embedding subgraphs and coloring graphs under extremal degree conditions, Ph. D. Thesis, Ohio State Univ., Columbus (1976)

  32. Chen, G., Enomoto, H., Kawarabayashi, K., Ota, K., Lou, D., Saito, A.: Vertex-disjoint cycles containing specified edges in a bipartite graph. Australas. J. Comb. 23, 37–48 (2001)

    MathSciNet  MATH  Google Scholar 

  33. Chen, G., Enomoto, H., Kawarabayashi, K., Ota, K., Lou, D., Saito, A.: Vertex-disjoint cycles containing specified vertices in a bipartite graph. J. Graph Theory 46, 145–166 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  34. Chen, G., Faudree, R.J., Gould, R.J., Jacobson, M.S., Lesniak, L.: Cycles in 2-factors of balanced bipartite graphs. Graphs Comb. 16, 67–80 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  35. Chen, G., Gould, R.J., Hirohata, K., Ota, K., Shan, S.: Disjoint chorded cycles of the same length. SIAM J. Discrete Math. 29, 1030–1041 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  36. Chen, G., Gould, R.J., Jacobson, M.S.: On 2-factors containing 1-factors in bipartite graphs. Discrete Math. 197–198, 185–194 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  37. Chen, G., Gould, R.J., Kawarabayashi, K., Ota, K., Saito, A., Schiermeyer, I.: The Chvátal-Erdős condition and 2-factors with a specified number of components. Discuss. Math. Graph Theory 27, 401–407 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  38. Chen, G., Saito, A.: Graphs with a cycle of length divisible by three. J. Comb. Theory Ser. B 60, 277–292 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  39. Chen, Y., Tian, F., Wei, B.: Degree sums and path-factors in graphs. Graphs Comb. 17, 61–71 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  40. Chiba, S.: On the difference between hamilton cycles and 2-factors with a prescribed number of cycles. Electr. Notes Discrete Math. 61, 239–245 (2017)

    Article  MATH  Google Scholar 

  41. Chiba, S., Egawa, Y., Yoshimoto, K.: A 2-factor in which each cycle contains a vertex in a specified stable set. Australas. J. Comb. 46, 203–210 (2010)

    MathSciNet  MATH  Google Scholar 

  42. Chiba, S., Fujita, S.: Covering vertices by a specified number of disjoint cycles, edges and isolated vertices. Discrete Math. 313, 269–277 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  43. Chiba, S., Fujita, S., Gao, Y., Li, G.: On a sharp degree sum condition for disjoint chorded cycles in graphs. Graphs Comb. 26, 173–186 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  44. Chiba, S., Fujita, S., Kawarabayashi, K., Sakuma, T.: Minimum degree conditions for vertex-disjoint even cycles in large graphs. Adv. Appl. Math. 54, 105–120 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  45. Chiba, S., Lichiardopol, N.: On the existence of vertex-disjoint subgraphs with high degree sum. Discrete Appl. Math. 236, 84–95 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  46. Chiba, S., Matsubara, R., Tsugaki, M.: Relationships between the length of a longest path and the relative length. Australas. J. Comb. 47, 91–107 (2010)

    MathSciNet  MATH  Google Scholar 

  47. Chiba, S., Tsugaki, M.: A degree sum condition for the existence of a path-factor. Ars Comb. 113, 441–450 (2014)

    MathSciNet  MATH  Google Scholar 

  48. Chiba, S., Yamashita, T.: A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs. Discrete Math. 340, 2871–2877 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  49. Chiba, S., Yamashita, T.: On directed 2-factors in digraphs and 2-factors containing perfect matchings in bipartite graphs, accepted in SIAM Journal on Discrete Math. (arXiv:1612.08904)

  50. Chiba, S., Yamashita, T.: Degree sum conditions for vertex-disjoint cycles passing through specified vertices. Discrete Math. 340, 678–690 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  51. Chvátal, V., Erdős, P.: A note on hamiltonian circuits. Discrete Math. 2, 111–113 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  52. Coll, V., Halperin, A., Magnant, C., Salehi-Nowbandegani, P.: Enomoto and Ota’s conjecture holds for large graphs, arXiv:1408.0408

  53. Corrádi, K., Hajnal, A.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hung. 14, 423–439 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  54. Cream, M., Faudree, R.J., Gould, R.J., Hirohata, K.: Chorded cycles. Graphs Comb. 32, 2295–2313 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  55. Csaba, B., Shokoufandeh, A., Szemerédi, E.: Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three, Paul Erdős and his mathematics (Budapest, 1999). Combinatorica 23, 35–72 (2003)

    Article  MathSciNet  Google Scholar 

  56. Csóka, E., Lo, I., Norin, S., Wu, H., Yepremyan, L.: The extremal function for disconnected minors. J. Comb. Theory Ser. B 126, 162–174 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  57. Czipszer, J.: Solution to problem 127 (Hungarian). Mat. Lapok 14, 373–374 (1963)

    Google Scholar 

  58. Czygrinow, A., DeBiasio, L., Kierstead, H.A.: 2-factors of bipartite graphs with asymmetric minimum degrees. SIAM J. Discrete Math. 24, 486–504 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  59. DeBiasio, L., Ferrara, M., Morris, T.: Improved degree conditions for 2-factors with \(k\) cycles in hamiltonian graphs. Discrete Math. 320, 51–54 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  60. Diestel, R.: Graph theory, 4th edition. In: Axler, S., Ribet, K.A. (eds.) Graduate Texts in mathematics, 173. Springer, Heidelberg (2010)

    Google Scholar 

  61. Dirac, G.A.: Some theorems on abstract graphs. Proc. Lond. Math. Soc. 2, 69–81 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  62. Dirac, G.A.: On the maximal number of independent triangles in graphs. Abh. Math. Semin. Univ. Hamb. 26, 78–82 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  63. Dirac, G.A.: Some results concerning the structure of graphs. Can. Math. Bull. 6, 183–210 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  64. Dirac, G.A., Erdős, P.: On the maximal number of independent circuits in a graph. Acta Math. Acad. Sci. Hung. 14, 79–94 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  65. Diwan, A.: Decomposing graphs with girth at least five under degree constraints. J. Graph Theory 33, 237–239 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  66. Dong, J.: Small cycles and 2-factor passing through any given vertices in graphs. J. Appl. Math. Comput. 34, 485–493 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  67. Dong, J., Li, X.: An improved Fan-type degree condition for \(k\)-linked graphs. Ars Comb. 121, 275–279 (2015)

    MathSciNet  MATH  Google Scholar 

  68. Egawa, Y.: Vertex-disjoint cycles of the same length. J. Comb. Theory Ser. B 66, 168–200 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  69. Egawa, Y., Enomoto, H., Faudree, R.J., Li, H., Schiermeyer, I.: Two-factors each component of which contains a specified vertex. J. Graph Theory 43, 188–198 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  70. Egawa, Y., Faudree, R.J., Györi, E., Ishigami, Y., Schelp, R.H., Wang, H.: Vertex-disjoint cycles containing specified edges. Graphs Comb. 16, 81–92 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  71. Egawa, Y., Fujita, S., Kawarabayashi, K., Wang, H.: Existence of two disjoint long cycles in graphs. Discrete Math. 305, 154–169 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  72. Egawa, Fujita, Ota and Sakuma, in preparation

  73. Egawa, Y., Hagita, M., Kawarabayashi, K., Wang, H.: Covering vertices of a graph by \(k\) disjoint cycles. Discrete Math. 270, 115–125 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  74. Egawa, Y., Ota, K.: Vertex-disjoint paths in graphs. Ars Comb. 61, 23–31 (2001)

    MathSciNet  MATH  Google Scholar 

  75. El-Zahár, M.H.: On circuits in graphs. Discrete Math. 50, 227–230 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  76. Enomoto, H.: Graph decompositions without isolated vertices. J. Comb. Theory Ser. B 63, 111–124 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  77. Enomoto, H.: On the existence of disjoint cycles in a graph. Combinatorica 18, 487–492 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  78. Enomoto, H.: Graph partition problems into cycles and paths. Discrete Math. 233, 93–101 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  79. Enomoto, H., Kaneko, A., Tuza, Z.S.: \(P_{3}\)-factor and covering cycles in graphs of minimum degree \(\frac{n}{3}\), Colloq. Math. Soc. Janos Bolyai 52. Combinatorics Eger Hungary (1987)

  80. Enomoto, H., Li, H.: Partition of a graph into cycles and degenerated cycles. Discrete Math. 276, 177–181 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  81. Enomoto, H., Matsumura, H.: Cycle-partitions with specified vertices and edges. Ars Comb. 91, 33–51 (2009)

    MathSciNet  MATH  Google Scholar 

  82. Enomoto, H., Ota, K.: Partitions of a graph into paths with prescribed endvertices and lengths. J. Graph Theory 34, 163–169 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  83. Erdős, P.: Problem 9. In: Fiedler, M. (ed.) Theory of Graphs and its Applications Czech. p. 159, Academy of Sciences, Prague (1964)

  84. Erdős, P.: Some recent combinatorial problems, Technical Report, University of Bielefeld (Nov. 1990)

  85. Erdős, P., Gallai, T.: On maximal paths and circuits of graphs. Acta Math. Acad. Sci. Hung. 10, 337–356 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  86. Erdős, P., Pósa, L.: On the maximal number of disjoint circuits of a graph. Publ. Math. Debr. 9, 3–12 (1962)

    MathSciNet  MATH  Google Scholar 

  87. Erdős, P., Pósa, L.: On independent circuits contained in a graph. Can. J. Math. 17, 347–352 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  88. Fan, G.H.: New sufficient conditions for cycles in graphs. J. Comb. Theory Ser. B 37, 221–227 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  89. Fan, G., Kierstead, H.A.: Hamiltonian square-paths. J. Comb. Theory Ser. B 67, 167–182 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  90. Faudree, R.J., Gould, R.J.: A note on neighborhood unions and independent cycles. Ars Comb. 76, 29–31 (2005)

    MathSciNet  MATH  Google Scholar 

  91. Faudree, R.J., Gould, R.J.: Precise location of vertices on Hamiltonian cycles. Discrete Math. 313, 2772–2777 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  92. Faudree, R.J., Gould, R.J., Jacobson, M., Lesniak, L., Saito, A.: Toughness, degrees and 2-factors. Discrete Math. 286, 245–249 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  93. Faudree, R.J., Gould, R.J., Jacobson, M., Lesniak, L., Saito, A.: A note on 2-factors with two components. Discrete Math. 300, 218–224 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  94. Ferrara, M., Gould, R.J.: \(H\)-linked graphs. In: Beineke, L.W., Wilson, R.J. (eds.) Topics in structural graph theory (Encyclopedia of Mathematics and its Applications 147). Cambridge University Press, Cambridge (2013)

    Google Scholar 

  95. Ferrara, M., Gould, R., Jacobson, M., Pfender, F., Powell, J., Whalen, T.: New Ore-type conditions for \(H\)-linked graphs. J. Graph Theory 71, 69–77 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  96. Ferrara, M., Gould, R.J., Tansey, G., Whalen, T.: On \(H\)-linked graphs. Graphs Comb. 22, 217–224 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  97. Ferrara, M.J., Jacobson, M.S., Powell, J.: Characterizing degree-sum maximal nonhamiltonian bipartite graphs. Discrete Math. 312, 459–461 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  98. Festa, P., Pardalos, P.M., Resenda, M.G.C.: Feedback set problems. In: Du, D.Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, Supplement, vol. A, pp. 209–258. Kluwer Acad. Publ., Dordrecht (1999)

    Chapter  Google Scholar 

  99. Finkel, D.: On the number of independent chorded cycle in a graph. Discrete Math. 308, 5265–5268 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  100. Fujita, S.: Partition of a graph into cycles and isolated vertices. Australas. J. Comb. 32, 79–89 (2005)

    MathSciNet  MATH  Google Scholar 

  101. Fujita, S.: Vertex-disjoint copies of \(K_{4}^{-}\) in graphs. Australas. J. Comb. 31, 189–200 (2005)

    MATH  Google Scholar 

  102. Fujita, S.: Degree conditions for the partition of a graph into cycles, edges and isolated vertices. Discrete Math. 309, 3534–3540 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  103. Fujita, S., Matsumura, H., Tsugaki, M., Yamashita, T.: Degree sum condition and vertex-disjoint cycles in a graph. Austras. J. Comb. 35, 237–255 (2006)

    MathSciNet  MATH  Google Scholar 

  104. Frank, A.: Problem proposed in the “Fifth British Combinatorial Conference”. Aberdeen, Scotland (1975)

    Google Scholar 

  105. Gallai, T.: Maximum-minimum Sätze and verallgemeinerte Faktoren von Graphen. Acta Math. Acad. Sci. Hung. 12, 131–173 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  106. Gao, Y., Li, G.: On the maximum number of disjoint chorded cycles in graphs. Ars Comb. 98, 415–422 (2011)

    MathSciNet  MATH  Google Scholar 

  107. Gao, Y., Li, G., Yan, J.: A vertex cover with chorded 4-cycles. Acta Math. Sin. 27, 2351–2360 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  108. Gao, Y., Li, G., Yan, J.: Neighborhood unions for the existence of disjoint chorded cycles in graphs. Graphs Comb. 29, 1337–1345 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  109. Gao, Y., Yan, J., Li, G.: On 2-factors with cycles containing specified vertices in a bipartite graph. J. Appl. Math. Comput. 31, 203–215 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  110. Gould, R.J., Hirohata, K., Horn, P.: Independent cycles and chorded cycles in graphs. J. Comb. 4, 105–122 (2013)

    MathSciNet  MATH  Google Scholar 

  111. Gould, R.J., Hirohata, K., Horn, P.: On independent doubly chorded cycles. Discrete Math. 338, 2051–2071 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  112. Gould, R.J., Hirohata, K., Keller, A.: On vertex-disjoint cycles and degree sum conditions. Discrete Math. 341, 203–212 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  113. Gould, R., Horn, P., Magnant, C.: Multiply chorded cycles. SIAM J. Discrete Math. 28, 160–172 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  114. Gould, R.J., Kostochka, A., Yu, G.: On minimum degree implying that a graph is \(H\)-linked. SIAM J. Discrete Math. 20, 829–840 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  115. Gould, R.J., Whalen, T.C.: Distance between two \(k\)-sets and path-systems extendibility. Ars Comb. 79, 211–228 (2006)

    MathSciNet  MATH  Google Scholar 

  116. Gould, R.J., Whalen, T.: Subdivision extendibility. Graphs Comb. 23, 165–182 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  117. Gould, R.J., Whalen, T.C.: Connectivity linkage, and hamilton path-systems in bipartite graphs, preprint. http://www.mathcs.emory.edu/~whalen/Articles/bip.pdf

  118. Gupta, R.P., Kahn, J., Robertson, N.: On the maximum number of diagonals of a circuit in a graph. Discrete Math. 32, 37–43 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  119. Györi, E.: On division of graphs to connected subgraphs, Combinatorics. In: Proc. Fifth Hungarian Colloq., Keszthely, 1976) I, pp. 485–494, Colloq. Math. Soc. János Bolyai 18, North-Holland, Amsterdam (1978)

  120. Häggkvist, R.: On \(F\)-hamiltonian graphs. In: “Graph Theory and Related Topics” (Proc. Conf., univ. Waterloo, Waterloo, Ont., 1977) pp. 219–231, Academic Press, New York-London (1979)

  121. Häggkvist, R.: Equicardinal disjoint cycles in sparse graphs. Ann. Discrete Math. 27, 269–274 (1985)

    MathSciNet  MATH  Google Scholar 

  122. Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdős. Comb. Theory Appl. 2, 601–623 (1970)

    MATH  Google Scholar 

  123. Hajnal, P.: Partition of graphs with condition on the connectivity and minimum degree. Combinatorica 3, 95–99 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  124. Hall, M., Magnant, C., Wang, H.: Note on Enomoto and Ota’s conjecture for short paths in large graphs. Graphs Comb. 30, 1463–1467 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  125. Harant, J., Rautenbach, D., Recht, P., Schiermeyer, I., Sprengel, E.-M.: Packing disjoint cycles over vertex cuts. Discrete Math. 310, 1974–1978 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  126. Harvey, D.J., Wood, D.R.: Cycles of given size in a dense graph. SIAM J. Discrete Math. 29, 2336–2349 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  127. Hayashi, K.: Number of disjoint 5-cycles in graphs. Ars Comb. 96, 295–320 (2010)

    MathSciNet  MATH  Google Scholar 

  128. Hu, Z., Li, H.: Weak cycle partition involving degree sum conditions. Discrete Math. 309, 647–654 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  129. Ishigami, Y.: Vertex-disjoint cycles of length at most four each of which contains a specified vertex. J. Graph Theory 37, 37–47 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  130. Ishigami, Y., Jiang, T.: Vertex-disjoint cycles containing prescribed vertices. J. Graph Theory 42, 276–296 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  131. Ishigami, Y., Wang, H.: An extension of a theorem on cycles containing specified independent edges. Discrete Math. 245, 127–137 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  132. Jiang, S., Yan, J.: Partial Degree Conditions and Cycle Coverings in Bipartite Graphs. Graphs Comb. 33, 955–967 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  133. Jiao, Z., Wang, H., Yan, J.: Disjoint cycles in graphs with distance degree sum conditions. Discrete Math. 340, 1203–1209 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  134. Johansson, R.: An El-Zahár type condition ensuring path-factors. J. Graph Theory 28, 39–42 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  135. Jung, H.A.: On maximal circuits in finite graphs. Ann. Discrete Math. 3, 129–144 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  136. Justesen, P.: On independent circuits in finite graphs and a conjecture of Erdős and Pósa. Ann. Discrete Math. 41, 299–306 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  137. Kakimura, N., Kawarabayashi, K., Marx, D.: Packing cycles through prescribed vertices. J. Comb. Theory Ser. B 101, 378–381 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  138. Kaneko, A.: On decomposition of triangle-free graphs under degree constraints. J. Graph Theory 27, 7–9 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  139. Kaneko, A., Yoshimoto, K.: On a 2-factor with a specified edge in a graph satisfying the Ore condition. Discrete Math. 257, 445–461 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  140. Kaneko, A., Yoshimoto, K.: A 2-factor with two components of a graph satisfying the Chvátal-Erdős condition. J. Graph Theory 43, 269–279 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  141. Kaneko, A., Yoshimoto, K.: On longest cycles in a balanced bipartite graph with Ore type condition. I, unpublished. http://trout.math.cst.nihon-u.ac.jp/~yosimoto/paper/longest_bip2_en.pdf

  142. Kára, J., Král, D.: Minimum degree and the number of chords. Ars Comb. 68, 169–179 (2003)

    MathSciNet  MATH  Google Scholar 

  143. Karp, R.M.: On the omputational complexity of combinatorial problems. Networks 5, 45–68 (1975)

    Article  MATH  Google Scholar 

  144. Kawarabayashi, K.: A study on Hamiltonian cycles and related topics, doctoral thesis, Keio University (2000)

  145. Kawarabayashi, K.: Graph partition into paths containing specified vertices. Discrete Math. 248, 271–277 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  146. Kawarabayashi, K.: \(K_{4}^{-}\)-factor in a graph. J. Graph Theory 39, 111–128 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  147. Kawarabayashi, K., Kostochka, A., Yu, G.: On sufficient degree conditions for a graph to be \(k\)-linked. Comb. Probab. Comput. 15, 685–694 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  148. Kierstead, H., Kostochka, A.: An Ore-type theorem on equitable coloring. J. Comb. Theory Ser. B 98, 226–234 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  149. Kierstead, H.A., Kostochka, A.V., McConvey, A.: Strengthening theorems of Dirac and Erdős on disjoint cycles. J Graph Theory 85, 788–802 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  150. Kierstead, H., Kostochka, A., Yeager, E.: On the Corrádi-Hajnal theorem and a question of Dirac. J. Comb. Theory Ser. B 122, 121–148 (2017)

    Article  MATH  Google Scholar 

  151. Kierstead, H., Kostochka, A., Yeager, E.: The \((2k--1)\)-connected multigraphs with at most \(k-1\) disjoint cycles. Combinatorica 37, 77–86 (2017)

    Article  MathSciNet  Google Scholar 

  152. Kierstead, H.A., Kostochka, A.V., Yu, G.: Extremal graph packing problems. In: Surveys in Combinatorics, in: London Math. Soc. Lecture Notes Series, vol. 365, Cambridge University Press, pp. 113–135 (2009)

  153. Komlós, J.: Tiling Turán theorems. Combinatorica 20, 203–218 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  154. Komlós, J., Sárközy, G.N., Szemerédi, E.: Proof of the Alon-Yuster conjecture. Discrete Math. 235, 255–269 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  155. Komlós, J., Sárközy, G.N., Szemerédi, E.: Proof of the Seymour conjecture for large graphs. Ann. Comb. 2, 43–60 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  156. Kostochka, A., Yu, G.: An extremal problem for \(H\)-linked graphs. J. Graph Theory 50, 321–339 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  157. Kostochka, A., Yu, G.: Ore-type graph packing problems. Comb. Prob. Comput. 16, 167–169 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  158. Kostochka, A.V., Yu, G.: Ore-type degree conditions for a graph to be \(H\)-linked. J. Graph Theory 58, 14–26 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  159. Kostochka, A., Yu, G.: Minimum degree conditions for \(H\)-linked graphs. Discrete Appl. Math. 156, 1542–1548 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  160. Kostochka, A., Yu, G.: Ore-type conditions implying 2-factors consisting of short cycles. Discrete Math. 309, 4762–4771 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  161. Kostochka, A., Yu, G.: Graphs containing every 2-factor. Graphs Comb. 28, 687–716 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  162. Kronk, H.V.: A note on \(k\)-path hamiltonian graphs. J. Comb. Theory Ser. B 7, 104–106 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  163. Kühn, D., Osthus, D.: Partitions of graphs with high minimum degree or connectivity. J. Comb. Theory Ser. B 88, 29–43 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  164. Kühn, D., Osthus, D.: The minimum degree threshold for perfect graph packings. Combinatorica 29, 65–107 (2009)

    Article  MathSciNet  Google Scholar 

  165. Kühn, D., Osthus, D., Treglown, A.: An Ore-type theorem for perfect packings in graphs. SIAM J. Discrete Math. 23, 1335–1355 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  166. Larman, D.G., Mani, P.: On the existence of certain configurations within graphs and the 1-skeletons of polytopes. Proc. Lond. Math. Soc. 20, 144–160 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  167. Las Vergnas, M.: Ph.D. Thesis, University of Paris (1972)

  168. Li, R., Ferrara, M., Zhang, X., Li, S.: A Fan-type degree condition for \(k\)-linked graphs. Australas. J. Comb. 57, 139–143 (2013)

    MathSciNet  MATH  Google Scholar 

  169. Li, F., Geng, J., Li, S., Liang, F.: A partition of bipartite graphs with 4-cycle and 8-cycle. J. Shandong Univ. (Nat. Sci.) 43(6), 1–4 (2008)

    MathSciNet  MATH  Google Scholar 

  170. Li, J., Steiner, G.: Partitioning a graph into vertex-disjoint paths. Studia Sci. Math. Hung. 42, 277–294 (2005)

    MathSciNet  MATH  Google Scholar 

  171. Li, J., Steiner, G.: Partitioning a bipartite graph into vertex-disjoint paths. Ars Comb. 81, 161–173 (2006)

    MathSciNet  MATH  Google Scholar 

  172. Li, X., Wei, B., Yang, F.: A degree condition of 2-factors in bipartite graphs. Discrete Appl. Math. 113, 311–318 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  173. Li, X., Wei, B., Yang, F.: Independent cycles in a bipartite graph. Ars Comb. 73, 173–186 (2004)

    MathSciNet  MATH  Google Scholar 

  174. Lichiardopol, N., Pór, At, Sereni, J.S.: A step toward the Bermond-Thomassen conjecture about disjoint cycles in digraphs. SIAM J. Discrete Math 23, 979–992 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  175. Lim, H.-S., Kim, H.-C., Park, J.-H.: Ore-type degree conditions for disjoint path covers in simple graphs. Discrete Math. 339, 770–779 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  176. Linial, N.: A lower bound for the circumference of a graph. Discrete Math. 15, 297–300 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  177. Liu, M., Xu, B.: Bipartition of graph under degree constrains. Sci. China Math. 58, 869–874 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  178. Lovász, L.: On graphs not containing independent circuits. Mat. Lapok (N.S.) 16, 289–299 (1965). (in Hungarian, English summary)

    MathSciNet  MATH  Google Scholar 

  179. Lovász, L.: Problem 4. In: Fiedler, M. (ed.) Recent advances in graph theory. p. 542, Academia, Prague, (1975)

  180. Lovász, L.: A homology theory for spanning trees of a graph. Acta Math. Acad. Sci. Hung. 30, 241–251 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  181. Lovász, L.: Matroid matching and some applications. J. Comb. Theory Ser. B 28, 208–236 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  182. Lovász, L.: Combinatorial problems and exercises. North-Holland Publishing Co., Amsterdam (1993)

    MATH  Google Scholar 

  183. Ma, F., Yan, J.: The confirmation of a conjecture on disjoint cycles in a graph. arXiv:1707.02390

  184. Marder, W.: Existenz \(n\)-fach zusammenhängender Teilgraphen in Graphen genügend grosser Kantendichte. Abh. Math. Sem. Univ. Hambg. 37, 86–97 (1972)

    Article  MATH  Google Scholar 

  185. Mader, W.: Üher die Maximalzahl kreuzungsfreier \(H\)-Wege. Arch. Math. (Basel) 31, 310–318 (1978)

    Article  MathSciNet  Google Scholar 

  186. Magnant, C., Martin, D.: An asymptotic version of a conjecture by Enomoto and Ota. J. Graph Theory 64, 37–51 (2010)

    MathSciNet  MATH  Google Scholar 

  187. Magnant, C., Ozeki, K.: Partitioning graphs into paths or cycles of prescribed lengths. J. Comb. 3, 135–161 (2012)

    MathSciNet  MATH  Google Scholar 

  188. Martin, R.R., Skokan, J.: Asymptotic multipartite version of the Alon-Yuster theorem. J. Comb. Theory Ser. B 127, 32–52 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  189. Matsubara, R., Matsumura, H.: Vertex disjoint cycles containing specified paths of order 3 in a bipartite graph. SUT J. Math. 41, 179–195 (2005)

    MathSciNet  MATH  Google Scholar 

  190. Matsubara, R., Matsumura, H.: Partition of a graph into cycles containing a specified linear forest. Discuss. Math. Graph Theory 28, 97–107 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  191. Matsubara, R., Matsumura, H., Tsugaki, M., Yamashita, T.: Degree sum conditions for path-factors with specified end vertices in bipartite graphs. Discrete Math. 340, 87–95 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  192. Matsubara, R., Sakai, T.: Cycles and degenerate cycles through specified vertices. Far East J. Appl. Math. 20, 201–208 (2005)

    MathSciNet  MATH  Google Scholar 

  193. Matsumura, H.: Vertex-disjoint 4-cycles containing specified edges in a bipartite graph. Discrete Math. 297, 78–90 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  194. Matsumura, H.: Vertex-disjoint short cycles containing specified edges in a graph. Ars Comb. 80, 147–152 (2006)

    MathSciNet  MATH  Google Scholar 

  195. Menger, Karl: Zur allegeminen Kurventheorie. Fundam. Math. 10, 95–115 (1927)

    Article  Google Scholar 

  196. Molla, T., Santana, M., Yeager, E.: A refinement of theorems of vertex-disjoint chorded cycles. Graphs Comb. 33, 181–201 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  197. Moon, J.W., Moser, L.: On hamiltonian bipartite graphs. Isr. J. Math. 1, 163–165 (1963)

    Article  MathSciNet  MATH  Google Scholar 

  198. Nara, C.: On sufficient conditions for a graph to be hamiltonian. Nat. Sci. Rep. Ochanomizu Univ. 31, 75–80 (1980)

    MathSciNet  MATH  Google Scholar 

  199. Niessen, T.: Minimum degree, independence number and regular factors. Graphs Comb. 11, 376–378 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  200. Ore, O.: Note on Hamilton circuits. Am. Math. Mon. 67, 55 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  201. Ore, O.: Hamilton connected graphs. J. Math. Pures Appl. 42, 21–27 (1963)

    MathSciNet  MATH  Google Scholar 

  202. Pontecorvi, M., Wollan, P.: Disjoint cycles intersecting a set of vertices. J. Comb. Theory Ser. B 102, 1134–1141 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  203. Pósa, L.: Problem no. 127 (Hungarian). Mat. Lapok 12, 254 (1961)

    Google Scholar 

  204. Qiao, S.: Neighborhood unions and disjoint chorded cycles in graphs. Discrete Math. 312, 891–897 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  205. Qiao, S., Zhang, S.: Vertex-disjoint chorded cycles in a graph. Oper. Res. Lett. 38, 564–566 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  206. Qiao, S., Zhang, S.: Spanning cyclic subdivisions of vertex-disjoint cycles and chorded cycles in graphs. Graphs Comb. 28, 277–285 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  207. Rautenbach, D., Regen, F.: Graphs with many vertex-disjoint cycles. Discrete Math. Theor. Comput. Sci. 14, 75–82 (2012)

    MathSciNet  MATH  Google Scholar 

  208. Reed, B.A., Wood, D.R.: Forcing a sparse minor. Comb. Prob. Comput. 25, 300–322 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  209. Saito, A.: Chvátal and Erdős Theorem: Old theorem with new aspects, Computational Geometry and Graph Theory, Lecture Notes in Comput. Sci. 4535, Springer, Berlin, 191–200 (2008)

  210. Sárközy, G.: On 2-factors with \(k\) components. Discrete Math. 308, 1962–1972 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  211. Sauer, N., Spencer, J.: Edge disjoint placement of graphs. J. Comb. Theory Ser. B 25, 295–302 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  212. Schmeichel, E., Hayes, D.: Some extensions of Ore’s theorem. In: Alavi, Y. (ed.) Graph theory and its applications to algorithms and computer science, pp. 687–695. Wiley, New York (1985)

    Google Scholar 

  213. Schrijver, A.: A short proof of Mader’s \(\cal{S}\)-paths theorem. J. Comb. Theory Ser. B 82, 319–321 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  214. Seymour, P.: Problem section. In: McDonough, T.P., Mavron, V.C. (eds.) Combinatorics. In: Proceedings of the British Combinatorial Conference 1973, Cambridge University Press, Cambridge. 201–202 (1974)

  215. Shi, R.H.: 2-neighborhoods and hamiltonian conditions. J. Graph Theory 16, 267–271 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  216. Stiebitz, M.: Decomposing graphs under degree constraints. J. Graph Theory 23, 321–324 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  217. Thomas, R., Wollan, P.: An improved linear edge bound for graph linkages. Eur. J. Combin. 26, 309–324 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  218. Thomassen, C.: Nonseparating cycles in \(k\)-connected graphs. J. Graph Theory 5, 351–354 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  219. Thomassen, C.: Disjoint cycles in digraphs. Combinatorica 3, 393–396 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  220. Thomassen, C.: Girth in graphs. J. Comb. Theory Ser. B 31, 129–141 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  221. Thomassen, C.: Graph decomposition with constraints on the connectivity and minimum degree. J. Graph Theory 7, 165–167 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  222. Thomassen, C.: Graph decomposition with applications to subdivisions and path systems modulo \(k\). J. Graph Theory 7, 261–271 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  223. Thomassen, C.: On the presence of disjoint subgraphs of a specified type. J. Graph Theory 12, 101–111 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  224. Thomassen, C.: Paths, circuits and subdivisions. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory III, pp. 97–131. Academic Press, New York (1988)

  225. Tutte, W.T.: The factors of graphs. Can. J. Math. 4, 314–328 (1952)

    Article  MATH  Google Scholar 

  226. Versträete, J.: Vertex-disjoint cycles of the same length. J. Comb. Theory Ser. B 88, 45–52 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  227. Wang, H.: Independent cycles with limited size in a graph. Graphs Comb. 10, 271–281 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  228. Wang, H.: Covering a graph with cycles. J. Graph Theory 20, 203–211 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  229. Wang, H.: Two vertex-disjoint cycles in a graph. Graphs Comb. 11, 389–396 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  230. Wang, H.: On the maximum number of independent cycles in a bipartite graph. J. Comb. Theory Ser. B 67, 152–164 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  231. Wang, H.: Covering a graph with cycles passing through given edges. J. Graph Theory 26, 105–109 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  232. Wang, H.: Vertex-disjoint hexagons with chords in a bipartite graph. Discrete Math. 187, 221–231 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  233. Wang, H.: On the maximum number of independent cycles in a graph. Discrete Math. 205, 183–190 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  234. Wang, H.: On 2-factors of a bipartite graph. J. Graph Theory 31, 101–106 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  235. Wang, H.: Proof of a conjecture on cycles in a bipartite graph. J. Graph Theory 31, 333–343 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  236. Wang, H.: On vertex-disjoint complete bipartite subgraphs in a bipartite graph. Graphs Comb. 15, 353–364 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  237. Wang, H.: Large vertex-disjoint cycles in a bipartite graph. Graphs Comb. 16, 359–366 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  238. Wang, H.: On quadrilaterals and cycle covers in a bipartite graph. Ars Comb. 58, 301–311 (2001)

    MathSciNet  MATH  Google Scholar 

  239. Wang, H.: Maximal total length of k disjoint cycles in bipartite graphs. Combinatorica 25, 367–377 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  240. Wang, H.: Disjoint triangles and quadrilaterals in a graph. Cent. Eur. J. Math. 6, 543–558 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  241. Wang, H.: Proof of the Erdős-Faudree conjecture on quadrilaterals. Graphs Comb. 26, 833–877 (2010)

    Article  MATH  Google Scholar 

  242. Wang, H.: An extension of the Corrádi-Hajnal theorem. Australas. J. Comb. 54, 59–84 (2012)

    MATH  Google Scholar 

  243. Wang, H.: Disjoint 5-cycles in a graph. Discuss. Math. Graph Theory 32, 221–242 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  244. Wang, H.: Disjoint long cycles in a graph. Sci. China Math. 56, 1983–1998 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  245. Wang, H.: Disjoint cycles with prescribed lengths and independent edges in graphs. J. Korean Math. Soc. 51, 919–940 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  246. Wang, H.: Partial degree conditions and cycle coverings. J. Graph Theory 78, 295–304 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  247. Woodall, D.R.: Sufficient conditions for circuits in graphs. Proc. Lond. Math. Soc. 24, 739–755 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  248. Yamashita, T.: On degree sum conditions for long cycles and cycles through specified vertices. Discrete Math. 308, 6584–6587 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  249. Yan, J.: Disjoint triangles and quadrilaterals in a graph. Discrete Math. 308, 3930–3937 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  250. Yan, J., Gao, Y.: On Enomoto’s problems in a bipartite graph. Sci. China Ser. A 52, 1947–1954 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  251. Yan, J., Liu, G.Z.: On 2-factors with prescribed properties in a bipartite graph. Acta Math. Sin. (Engl. Ser.) 22, 1115–1120 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  252. Yan, J., Liu, G.: On 2-factors with quadrilaterals containing specified vertices in a bipartite graph. Ars Comb. 82, 133–144 (2007)

    MathSciNet  MATH  Google Scholar 

  253. Yan, J., Liu, G.Z.: On 2-factors with cycles containing specified edges in a bipartite graph. Discrete Math. 309, 1112–1117 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  254. Yan, J., Zhang, S., Cai, J.: Fan-type condition on disjoint cycles in a graph. Discrete Math. https://doi.org/10.1016/j.disc.2017.09.027

  255. Zamani, R., West, D.B.: Spanning cycles through specified edges in bipartite graphs. J. Graph Theory 71, 1–17 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  256. Zhang, X., Wu, J.-J., Yan, J.: Degree conditions for the partition of a graph into triangles and quadrilaterals. Util. Math. 86, 341–346 (2011)

    MathSciNet  MATH  Google Scholar 

  257. Zhang, S., Yan, J., Jiang, S.: Vertex-disjoint cycles containing specified vertices in a bipartite graph. Graphs Comb. 32, 2171–2181 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  258. Zhang, Z.B., Zhang, X., Wen, X.: Directed hamilton cycles in digraphs and matching alternating hamilton cycles in bipartite graphs. SIAM J. Discrete Math. 27, 274–289 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  259. Zhao, Y.: Bipartite graph tiling. SIAM J. Discrete Math. 23, 888–900 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  260. Zou, Q., Chen, H., Li, G.: Vertex-disjoint cycles of order eight with chords in a bipartite graph. Bull. Malays. Math. Sci. Soc. (2) 36, 255–262 (2013)

    MathSciNet  MATH  Google Scholar 

  261. Zou, Q., Li, G., Dong, A.: Ore-type conditions for bipartite graphs containing hexagons. Discrete Math. 311, 1658–1665 (2011)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank Dr. Ryota Matsubara, Dr. Hajime Matsumura, Dr. Kenta Ozeki and Dr. Masao Tsugaki for their helpful comments and suggestions. Also, the authors would like to thank the referees for their helpful comments and corrections.

Author information

Authors and Affiliations

  1. Applied Mathematics, Faculty of Advanced Science and Technology, Kumamoto University, 2-39-1 Kurokami, Kumamoto, 860-8555, Japan

    Shuya Chiba

  2. Department of Mathematics, Kindai University, 3-4-1 Kowakae, Higashi-Osaka, Osaka, 577-8502, Japan

    Tomoki Yamashita

Authors
  1. Shuya Chiba
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomoki Yamashita
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shuya Chiba.

Additional information

First author’s work was supported by JSPS KAKENHI Grant Number 17K05347, 17K05348 and by Grant for Basic Research Projects from the Sumitomo Foundation (Grant number 170149). Second author’s work was supported by JSPS KAKENHI Grant Number 16K05262.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chiba, S., Yamashita, T. Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey. Graphs and Combinatorics 34, 1–83 (2018). https://doi.org/10.1007/s00373-017-1873-5

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-017-1873-5

Keywords

Search

Navigation