Degree Sequences of Edge-Colored Graphs in Specified Families and Related Problems

Abstract Movement has been made in recent times to generalize the study of degree sequences to k-edge-colored graphs and doing so requires the notion of a degree vector<\italic>. The degree vector of a vertex v<\italic> in a k-edge-colored graph is a column vector in which entry i<\italic> indicates the number of edges of color i<\italic> incident to v<\italic>. Consider the following question which we refer to as the <\italic>k-Edge-Coloring Problem<\italic>. Given a set of column vectors C<\italic> and a graph family F<\italic>, when does there exist some k-edge-colored graph in F<\italic> whose set of degree vectors is C<\italic>? This question is NP-Complete in general but certain graph families yield tractable results. In this document, I present results on the k-Edge-Coloring Problem and the related Factor Problem for the following families of interest: unicyclic graphs, disjoint unions of paths (DUPs), disjoint union of cycles (DUCs), grids, and 2-trees.