{'fraction_non_alphanumeric': 0.028925619834710745, 'fraction_numerical': 0.0, 'mean_word_length': 5.333333333333333, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
r-partite Covers of Graphs

We formulate three new NP-hard optimization problems, namely the Minimum r-partite Cover (MRC) problem, the Minimum Connected r-partite Cover (MCRC) problem and the Minimum Connected r-partite Decomposition (MCRD) problem. These problems generalize the various known problems of covering the edges of a graph with a minimum number of bipartite subgraphs. We define new graph parameters, namely r-particity, connected r-particity and r-decomposability of a graph as the minimum number of subgraphs in a solution of MRC, MCRC and MCRD problems respectively. We obtain integer programming formulations and heuristic algorithms for solving these optimization problems and study the relationship of the newly defined parameters with each other and with other well-known graph parameters like the chromatic number. Furthermore, Nordhaus-Gaddum type theorems are established for the r-particity to better understand the behavior of this parameter.