The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
From MaRDI portal
Publication:6144493
DOI10.1007/s00373-023-02732-xMaRDI QIDQ6144493
Publication date: 29 January 2024
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Unnamed Item
- Unnamed Item
- Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths
- Packing 3-vertex paths in claw-free graphs and related topics
- Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph
- Packings by cliques and by finite families of graphs
- A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
- On maximum \(P_3\)-packing in claw-free subcubic graphs
- Some existence theorems on path factors with given properties in graphs
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- The path partition problem and related problems in bipartite graphs
- On packing 3-vertex paths in a graph
- Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
- On the Complexity of General Graph Factor Problems
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
- Path factors in cubic graphs
- Factors and factorizations of graphs—a survey
- Packings by Complete Bipartite Graphs
- On Restricted Two-Factors
- Linear-time computability of combinatorial problems on series-parallel graphs
- Path factors of bipartite graphs
- How many disjoint 2-edge paths must a cubic graph have?
- TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS
- Parallel Processing and Applied Mathematics
- The \(K_r\)-packing problem
This page was built for publication: The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices
