Degree conditions for the existence of vertex-disjoint cycles and paths: a survey

DOI10.1007/s00373-017-1873-5zbMath1382.05017OpenAlexW2789747582MaRDI QIDQ1706420

Tomoki Yamashita, Shuya Chiba

Publication date: 22 March 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-017-1873-5

zbMATH Keywords

pathspartitioningcyclespackingdegree conditions

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex degrees (05C07)

Related Items

Unnamed Item, The confirmation of a conjecture on disjoint cycles in a graph, On degree sum conditions for 2-factors with a prescribed number of cycles, Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree, Disjoint cycles covering specified vertices in bipartite graphs with partial degrees, Degree sum condition on distance 2 vertices for Hamiltonian cycles in balanced bipartite graphs, Properly colored cycles of different lengths in edge-colored complete graphs, Lichiardopol's conjecture on disjoint cycles in tournaments, Perfect matching in bipartite hypergraphs subject to a demand graph, Edge-disjoint properly colored cycles in edge-colored complete graphs, Partitioning the vertices of a digraph into directed cycles and degenerated directed cycles, Unnamed Item, Unnamed Item, On degree sum conditions for directed path-factors with a specified number of paths, An improvement of Lichiardopol's theorem on disjoint cycles in tournaments, Disjoint cycles and \(2\)-factors with Fan-type condition in a graph

Uses Software

• cyclechord

Cites Work

• Disjoint cycles in graphs with distance degree sum conditions
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
• Asymptotic multipartite version of the Alon-Yuster theorem
• Partial degree conditions and cycle coverings in bipartite graphs
• On vertex-disjoint cycles and degree sum conditions
• Minimum degree conditions for vertex-disjoint even cycles in large graphs
• Disjoint long cycles in a graph
• Independet cycles and chorded cycles in graphs
• The Erdős-Pósa property for long circuits
• An Ore-type theorem on equitable coloring
• On \(H\)-linked graphs
• On 2-factors with prescribed properties in a bipartite graph
• Bipartition of graph under degree constraints
• On the number of independent chorded cycles in a graph
• Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte
• A note on Hamiltonian circuits
• Vertex-disjoint 4-cycles containing specified edges in a bipartite graph
• A note on 2-factors with two components
• Existence of two disjoint long cycles in graphs
• On Hamiltonian bipartite graphs
• Vertex-disjoint cycles of length at most four each of which contains a specified vertex
• Minimum degree thresholds for bipartite graph tiling
• Degree conditions for the partition of a graph into triangles and quadrilaterals
• Spanning Cycles Through Specified Edges in Bipartite Graphs
• New Ore-Type Conditions for H-Linked Graphs
• An asymptotic version of a conjecture by Enomoto and Ota
• DISJOINT CYCLES WITH PRESCRIBED LENGTHS AND INDEPENDENT EDGES IN GRAPHS
• Note on Hamilton Circuits
• On maximal paths and circuits of graphs
• On Sufficient Degree Conditions for a Graph to be $k$-linked
• Ore-type graph packing problems
• Cycles of Given Size in a Dense Graph
• Chvátal Erdős condition and 2-factors with a specyfied number of components
• Partitions of a graph into cycles containing a specified linear forest
• Cyclability in bipartite graphs
• Bipartite Graph Tiling
• A Step toward the Bermond–Thomassen Conjecture about Disjoint Cycles in Digraphs
• An Ore-type Theorem for Perfect Packings in Graphs
• Disjoint cycles with chords in graphs
• Graph decomposition with constraints on the connectivity and minimum degree
• Graph decomposition with applications to subdivisions and path systems modulo k
• Conditions for the Existence of Hamiltonian Circuits in Graphs Based on Vertex Degrees
• On the presence of disjoint subgraphs of a specified type
• Cycles in digraphs– a survey
• Nonseparating cycles inK-Connected graphs
• 2‐neighborhoods and hamiltonian conditions
• On the Computational Complexity of Combinatorial Problems
• On Maximal Circuits in Finite Graphs
• A homology theory for spanning tress of a graph
• [https://portal.mardi4nfdi.de/wiki/Publication:4242796 An El-Zah�r type condition ensuring path-factors]
• Independence trees and Hamilton cycles
• On 2-factors of a bipartite graph
• Proof of a conjecture on cycles in a bipartite graph
• Embedding Arbitrary Graphs of Maximum Degree Two
• Degree conditions for 2-factors
• Covering a graph with cycles passing through given edges
• On decomposition of triangle-free graphs under degree constraints
• Two‐factors each component of which contains a specified vertex
• A 2‐factor with two components of a graph satisfying the Chvátal‐Erdös condition
• Vertex-disjoint cycles containing specified vertices in a bipartite graph
• Partitions of a graph into paths with prescribed endvertices and lengths
• K₄⁻‐factor in a graph
• On Directed 2-factors in Digraphs and 2-factors Containing Perfect Matchings in Bipartite Graphs
• Long cycles through prescribed vertices have the Erdős‐Pósa property
• Disjoint 5-cycles in a graph
• Problems and results on judicious partitions
• Vertex‐disjoint cycles containing prescribed vertices
• Covering a graph with cycles
• Decomposing graphs with girth at least five under degree constraints
• Strengthening Theorems of Dirac and Erdős on Disjoint Cycles
• Multiply Chorded Cycles
• Partial Degree Conditions and Cycle Coverings
• Disjoint Chorded Cycles of the Same Length
• Directed Hamilton Cycles in Digraphs and Matching Alternating Hamilton Cycles in Bipartite Graphs
• Chvátal–Erdős Theorem: Old Theorem with New Aspects
• On Independent Circuits Contained in a Graph
• Decomposing Weighted Graphs
• Forcing a sparse minor
• Ore‐type degree conditions for a graph to be H‐linked
• 2-Factors of Bipartite Graphs with Asymmetric Minimum Degrees
• On Minimum Degree Implying That a Graph is H‐Linked
• Partitioning a graph into vertex-disjoint paths
• Some Results Concerning the Structure of Graphs
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• A note on K-path hamiltonian graphs
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Sufficient Conditions for Circuits in Graphs^†
• An extremal problem for H‐linked graphs
• On the maximal number of independent circuits in a graph
• On the maximal number of independent circuits in a graph
• Some Theorems on Abstract Graphs
• The Factors of Graphs
• Disjoint triangles and quadrilaterals in a graph
• Disjoint triangles and quadrilaterals in a graph
• Graph partition problems into cycles and paths
• Degree sums and path-factors in graphs
• Proof of the Alon-Yuster conjecture
• A degree condition of 2-factors in bipartite graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex-disjoint cycles containing specified vertices in a bipartite graph
• On the Corrádi-Hajnal theorem and a question of Dirac
• Neighborhood unions for the existence of disjoint chorded cycles in graphs
• Precise location of vertices on Hamiltonian cycles
• Improved degree conditions for 2-factors with \(k\) cycles in Hamiltonian graphs
• Note on Enomoto and Ota's conjecture for short paths in large graphs
• Chorded cycles
• Degree sum conditions for vertex-disjoint cycles passing through specified vertices
• Disjoint cycles in digraphs
• On a sharp degree sum condition for disjoint chorded cycles in graphs
• Proof of the Erdős-Faudree conjecture on quadrilaterals
• Vertex-disjoint chorded cycles in a graph
• Characterizing degree-sum maximal nonhamiltonian bipartite graphs
• Cycles through specified vertices
• Small cycles and 2-factor passing through any given vertices in graphs
• Disjoint cycles intersecting a set of vertices
• Edge disjoint placement of graphs
• Neighborhood unions and disjoint chorded cycles in graphs
• Hamilton connected graphs
• Partition of graphs with condition on the connectivity and minimum degree
• Girth in graphs
• On circuits in graphs
• New sufficient conditions for cycles in graphs
• Subdivision extendibility
• Efficient algorithms for decomposing graphs under degree constraints
• Ore-type degree conditions for disjoint path covers in simple graphs
• Minimum degree conditions for \(H\)-linked graphs
• On 2-factors with \(k\) components
• Packing disjoint cycles over vertex cuts
• On degree sum conditions for long cycles and cycles through specified vertices
• Disjoint chorded cycles in graphs
• Weak cycle partition involving degree sum conditions
• On 2-factors with cycles containing specified edges in a bipartite graph
• Degree conditions for the partition of a graph into cycles, edges and isolated vertices
• On pseudo 2-factors
• On 2-factors with cycles containing specified vertices in a bipartite graph
• On Enomoto's problems in a bipartite graph
• Ore-type conditions implying 2-factors consisting of short cycles
• Proof of a conjecture of Haeggkvist on cycles and independent edges
• Partition of a bipartite Hamiltonian graph into two cycles
• Disjoint directed cycles
• On the maximal number of independent triangles in graphs
• Matroid matching and some applications
• On the maximum number of diagonals of a circuit in a graph
• A lower bound for the circumference of a graph
• A remark on two sufficient conditions for Hamilton cycles
• Packings of graphs and applications to computational complexity
• Proof of the Seymour conjecture for large graphs
• On 2-factors containing 1-factors in bipartite graphs
• On the maximum number of independent cycles in a graph
• On the existence of disjoint cycles in a graph
• Graphs with a cycle of length divisible by three
• Independent cycles with limited size in a graph
• An extension of a theorem on cycles containing specified independent edges
• Partitions of graphs with high minimum degree or connectivity.
• Vertex-disjoint cycles of the same length.
• Covering vertices of a graph by \(k\) disjoint cycles
• Partition of a graph into cycles and degenerated cycles
• Vertex-disjoint hexagons with chords in a bipartite graph
• Tiling Turán theorems
• Large vertex-disjoint cycles in a bipartite graph
• Graph partition into paths containing specified vertices
• The confirmation of a conjecture on disjoint cycles in a graph
• Decompositions of graphs into cycles with chords
• On the difference between Hamilton cycles and 2-factors with a prescribed number of cycles
• On the existence of vertex-disjoint subgraphs with high degree sum
• Fan-type condition on disjoint cycles in a graph
• The \((2k-1)\)-connected multigraphs with at most \(k-1\) disjoint cycles
• Enomoto and Ota's conjecture holds for large graphs
• An improved linear edge bound for graph linkages
• On vertex-disjoint complete bipartite subgraphs in a bipartite graph
• On a 2-factor with a specified edge in a graph satisfying the Ore condition
• A short proof of Mader's \(\mathcal S\)-paths theorem
• Proof of a conjecture of Bollobás and Eldridge for graphs of maximum degree three
• Toughness, degrees and 2-factors
• Graph decompositions without isolated vertices
• Minimum degree, independence number and regular factors
• Two vertex-disjoint cycles in a graph
• On independent cycles and edges in graphs
• 2-factors in dense graphs
• Vertex-disjoint cycles of the same length
• \(H\)-factors in dense graphs
• On the maximum number of independent cycles in a bipartite graph
• Hamiltonian square-paths
• Graphs containing every 2-factor
• Spanning cyclic subdivisions of vertex-disjoint cycles and chorded cycles in graphs
• Covering vertices by a specified number of disjoint cycles, edges and isolated vertices
• Partitioning graphs into paths or cycles of prescribed lengths
• Vertex-disjoint cycles of order eight with chords in a bipartite graph
• A vertex cover with chorded 4-cycles
• Cycles in 2-factors of balanced bipartite graphs
• Vertex-disjoint cycles containing specified edges
• The minimum degree threshold for perfect graph packings
• Ore-type conditions for bipartite graphs containing hexagons
• Packing cycles through prescribed vertices
• On independent doubly chorded cycles
• A refinement of theorems on vertex-disjoint chorded cycles
• Degree sum conditions for path-factors with specified end vertices in bipartite graphs
• Maximal total length of \(k\) disjoint cycles in bitpartite graphs
• The extremal function for disconnected minors