Fair Factorizations of the Complete Multipartite Graphs and Related Edge-colorings

Abstract

In this dissertation, first the technique of vertex amalgamations is used to extend known results on graph decompositions, and in particular on decompositions of the complete multipartite graph K(n,p) with p parts, each of which has n vertices. The decompositions focus on hamilton cycles and 1-factors that satisfy certain fairness notions, as well as frame versions of these results where each color class (as defined by the decompositions) spans all vertices except for those in one part. Second, some edge-coloring results are proved, extending theorems in the literature on edge-colorings with different fairness properties. Finally, a related new topic is introduced, focusing on equalizing the number of vertices in each color class of an edge-coloring.