Internally Fair Factorizations and Internally Fair Holey Factorizations with Prescribed Regularity

  • Aras Erzurumluoğlu
  • Chris A. Rodger
Keywords: Graph Decompositions, Fair Factorizations, Holey Factorizations, Prescribed Regularity


Let $G$ be a multipartite multigraph without loops. Then $G$ is said to be internally fair if its edges are shared as evenly as possible among all pairs of its partite sets. An internally fair factorization of $G$ is an edge-decomposition of $G$ into internally fair regular spanning subgraphs. A holey factor of $G$ is a regular subgraph spanning all vertices but one partite set. An internally fair holey factorization is an edge-decomposition of $G$ into internally fair holey factors. In this paper, we settle the existence of internally fair (respectively, internally fair holey) factorizations of the complete equipartite multigraph into factors (respectively, holey factors) with prescribed regularity.

Article Number