Résumé | A graph G is said to be arbitrarily partitionable (AP for short) if for every partition (tau_1, ..., tau_p) of |V(G)| there exists a partition (V_1, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order tau_i. If, additionally, each of k of these subgraphs contains an arbitrary vertex of G prescribed beforehand, then G is said to be AP+k. Complete graphs on strictly more than k vertices are AP+k but are not convenient because of their size. In this talk, for any k ≠ 2 and n ≥ k+1, we will see that the Harary graph H_{k+1,n}, known to be one of the smallest (k+1)-connected graphs on n vertices, is AP+k. To overcome the fact that H_{3,n} is not AP+2 for some n, we will also introduce a class of edge-minimal 3-connected AP+2 graphs to complete our hierarchy of AP+k graphs with minimum size. These results are best possible in the sense that we cannot allow more prescriptions while partitioning these graphs.
Joint work with O. Baudon, J. Przybyło, E. Sopena, and M. Woźniak. |