Partitioning the Cartesian product of an arbitrarily partitionable graph and a complete graph

A graph G is arbitrarily partitionable (AP for short) if for every sequence (n_1, ..., n_p) of positive integers summing up to |V(G)| there exists a partition (V_1, ..., V_p) of V(G) such that G[V_i] is a connected graph on n_i vertices for every i in {1,...,p}. We show that the Cartesian product G x K_l is AP whenever G is AP and K_l is a complete graph on l >= 1 vertices.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00759291
Author Baudon, Olivier, Bensmail, Julien
Maintainer CCSD
Last Updated June 3, 2026, 03:55 (UTC)
Created June 3, 2026, 03:55 (UTC)
Identifier hal-00759291
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Bordelais de Recherche en Informatique (LaBRI) ; Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
creator Baudon, Olivier
date 2012-11-30T00:00:00
harvest_object_id b689b396-6bcd-48ca-b538-7e3ca19ae092
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-05-26T00:00:00
set_spec type:REPORT