报告题目：Use Topological Method to Partition a Graph into Connected Pieces

报告人：Peng Li, Chongqing University of Technology

报告时间： 9月8日  周五 下午4:30-5:30

报告地点：1218

摘要：

Let G be a simple graph with n vertices. Suppose 1 ≤ k ≤ n. We say G is k − good if for any subset{x1, x2, . . . , xk} of V (G) and any nonnegative integers n1, n2, . . . , nk with n1 + n2 + . . . + nk = n,we can always partition G to k connected pieces, say {G1, G2, . . . , Gk}, such that for every i ∈ [k], we have xi ∈ V (Gi) and |V (Gi)| = ni. In his paper Topological Methods in Combinatorics, Lovaszuse topological method to prove that any k-connected graph G is k − good. We use combinatorial method to prove that any k-connected graph G is k − good when k=2,3. We are interest in finding a combinatorial method to prove that any k-connected graph G is k − good for any integer k.

REFERENCES

[1] S.R. Arikati, C.P. Rangan, Linear algorithm for optimal path cover problem on interval

graphs, Information Processing Letters, 35 (1990), pp. 149�153.