Tighter bounds on the size of a maximum P₃-matching in a cubic graph

DOI10.1007/S00373-008-0807-7MaRDI QIDQ1014835zbMATH OpenOpenAlexFDO

Authors Adrian Kosowski, Michal Malafiejski, Paweł Żyliński

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)

Cites work

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

Cited in

(12)

• On maximum \(P_3\)-packing in claw-free subcubic graphs
• On partial descriptions of König graphs for odd paths and all their spanning supergraphs
• Minimum maximal matchings in cubic graphs
• scientific article; zbMATH DE number 1916558 (Why is no real title available?)
• König graphs with respect to the 4-path and its spanning supergraphs
• On the König graphs for a 5-path and its spanning supergraphs
• Maximum matchings in the \(n\)-dimensional cube
• 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
• The maximum 3-star packing problem in claw-free cubic graphs
• Packing 2- and 3-stars into ( 2 , 3 )-regular graphs
• Maximum bounded 3-dimensional matching is MAX SNP-complete

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014835)