报告题目：On maximum P3-packing in claw-free subcubic graphs
报告人：林文松 东南大学 教授
报告时间：2021年5月22日14:30-15:30
报告地点：数计学院20幢306
摘要：Let P3 denote the path on three vertices. A P3-packing of a given graph G is a collection of vertex-disjoint subgraphs of G in which each subgraph is isomorphic to P3. The maximum P3-packing problem is to and a P3-packing of a given graph G which contains the maximum number of vertices of G. The perfect P3-packing problem is to decide whether a graph G has a P3-packing that covers all vertices of G. Kelmans [A. Kelmans, Packing 3-vertex paths in claw-free graphs and related topics, Discrete Applied Mathematics 159(2011) 112-127] proposed the following problem: Is the P3-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the problem by proving that the perfect P3-packing problem in claw-free cubic planar graphs is NP-complete. In addition, we show that for any connected claw-free cubic graph (resp. (2; 3)-regular graph, subcubic graph) G with v(G) ≥14 (resp. v(G) ≥8, v(G) ≥3), the maximum P3-packing of G covers at least ⌈ (9v(G)-6)/10⌉ (resp.⌈ (6v(G)-6)/7⌉, ⌈(3v(G)-6)/4⌉) vertices, where v(G) denotes the order of G, and the bound is sharp.
The proofs imply polynomial-time algorithms.
邀请人：朱绪鼎