#### Date

2013

#### Document Type

Dissertation

#### Degree

Doctor of Philosophy

#### Department

Mathematics

#### First Adviser

Isaak, Garth

#### Other advisers/committee members

Coll, Vincent E.; Skandera, Mark; Michael, T. S.

#### 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.

#### Recommended Citation

Ryan, Kathleen Mae, "Degree Sequences of Edge-Colored Graphs in Specified Families and Related Problems" (2013). *Theses and Dissertations*. 1611.

http://preserve.lehigh.edu/etd/1611