Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph

DOI10.1007/s00373-008-0807-7zbMath1204.05077OpenAlexW2083270457MaRDI QIDQ1014835

Paweł Żyliński, Michał Małafiejski, Adrian Kosowski

Publication date: 29 April 2009

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

Full work available at URL: https://doi.org/10.1007/s00373-008-0807-7

zbMATH Keywords

cubic graphpath matchingthree-vertex path

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (6)

On the König graphs for a 5-path and its spanning supergraphs ⋮ Packing 2- and 3-stars into cubic graphs ⋮ The maximum 4-vertex-path packing of a cubic graph covers at least two-thirds of its vertices ⋮ On maximum \(P_3\)-packing in claw-free subcubic graphs ⋮ König Graphs with Respect to the 4-Path and Its Spanning Supergraphs ⋮ On partial descriptions of König graphs for odd paths and all their spanning supergraphs

Cites Work

• Unnamed Item
• An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs
• On the Complexity of General Graph Factor Problems
• Packingk-edge trees in graphs of restricted vertex degrees
• Path factors in cubic graphs
• Factors and factorizations of graphs—a survey
• How many disjoint 2-edge paths must a cubic graph have?

This page was built for publication: Tighter bounds on the size of a maximum \(P_{3}\)-matching in a cubic graph