报告题目：On maximum $P_3$-packing in claw-free subcubic graphs
报告人：林文松教授东南大学
报告时间：2021.6.3 9:30-10:30
地点：南山校区6号楼407
报告摘要：Let $P_3$ denote the path on three vertices. A $P_3$-packing of a given graph
$G$ is a collection of vertex-disjoint subgraphs of $G$ in which each subgraph is isomorphic
to $P_3$. The maximum $P_3$-packing problem is to find a $P_3$-packing of a given graph
$G$ which contains the maximum number of vertices of $G$. The perfect $P_3$-packing
problem is to decide whether a graph $G$ has a $P_3$-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
$P_3$-packing problem NP-hard in the class of claw-free graphs? In this paper, we solve the
problem by proving that the perfect $P_3$-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)\ge 14$ (resp. $v(G)\ge 8$, $v(G)\ge
3$), the maximum $P_3$-packing of $G$ covers at least $\lceil \frac{9v(G)-6}{10} \rceil$ (resp.
$\lceil \frac{6v(G)-6}{7} \rceil$, $\lceil \frac{3v(G)-6}{4} \rceil$) vertices, where $v(G)$ denotes
the order of $G$, and the bound is sharp. The proofs imply polynomial-time algorithms.
个人简介：林文松,东南大学数学学院教授、博士生导师。从事运筹学方面的教学和科研工作。主要研究方向：图论及其应用、网络最优化。先后主持国家自然科学基金面上项目3项，主持江苏省自然科学基金面上项目1项。已发表学术论文六十余篇。
