Packing 3-vertex paths in claw-free graphs and related topics

DOI10.1016/j.dam.2010.05.001zbMath1206.05058arXiv0910.4681OpenAlexW2072174759MaRDI QIDQ617645

Alexander K. Kelmans

Publication date: 21 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0910.4681

zbMATH Keywords

claw-free graphcubic graphgraph minorpath-factorgraph domination\(P_{3}\)-factor\(P_{3}\)-packingedge disjoint packinginduced packingthe Hadwiger conjecturevertex disjoint packing

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Related Items (12)

Component factors and binding number conditions in graphs ⋮ On path-factor critical deleted (or covered) graphs ⋮ Path factors in subgraphs ⋮ Some results about ID-path-factor critical graphs ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ Some existence theorems on path factors with given properties in graphs ⋮ Path-factor critical covered graphs and path-factor uniform graphs ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ Block allocation of a sequential resource ⋮ Some results on path-factor critical avoidable graphs ⋮ TOUGHNESS, ISOLATED TOUGHNESS AND PATH FACTORS IN GRAPHS ⋮ A \(5k\)-vertex kernel for \(P_2\)-packing

Cites Work

• Unnamed Item
• Matching theory
• Efficient subgraphs packing
• Optimal packing of induced stars in a graph
• 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 domination in connected cubic graphs
• On packing 3-vertex paths in a graph
• Hamiltonian results inK1,3-free graphs
• Packingk-edge trees in graphs of restricted vertex degrees
• Packings by Complete Bipartite Graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• How many disjoint 2-edge paths must a cubic graph have?
• Paths, Stars and the Number Three
• Asymptotically optimal tree-packings in regular graphs

This page was built for publication: Packing 3-vertex paths in claw-free graphs and related topics