On three polynomial kernels of sequences for arbitrarily partitionable graphs

A graph GG is arbitrarily partitionable if every sequence (n1,n2,…,np)(n1,n2,…,np) of positive integers summing up to |V(G)||V(G)| is realizable in GG, i.e.   there exists a partition (V1,V2,…,Vp)(V1,V2,…,Vp) of V(G)V(G) such that ViVi induces a connected subgraph of GG on nini vertices for every i∈{1,2,…,p}i∈{1,2,…,p}. Given a family F(n)F(n) of graphs with order n≥1n≥1, a kernel of sequences for F(n)F(n) is a set KF(n)KF(n) of sequences summing up to nn such that every member GG of F(n)F(n) is arbitrarily partitionable if and only if every sequence of KF(n)KF(n) is realizable in GG. We herein provide kernels with polynomial size for three classes of graphs, namely complete multipartite graphs, graphs with about a half universal vertices, and graphs made up of several arbitrarily partitionable components. Our kernel for complete multipartite graphs yields a polynomial-time algorithm to decide whether such a graph is arbitrarily partitionable.