Graph Edge Coloring and Extensions of Edge Colorings

This dissertation explores two main questions which may be framed in terms of graph edge-coloring. First, an assignment of $k$ colors to the edges of the complete bipartite graph $K_{n,n}$ corresponds to an assignment of $k$ symbols to the cells of an $n\times n$ array. Let $M$ be an $n\times n$ array whose top left $r\times s$ subarray is filled with symbols in $\{1,2,\dots,k\}$ such that $k\leq n^2$ and each cell contains exactly one symbol. We establish necessary and sufficient conditions that ensure the remaining cells of $M$ can each be assigned one symbol such that each symbol occurs a prescribed number of times in $M$ and the number of occurrences of each symbol in any given row or column of $M$ is within one of the number of occurrences of the symbol in any other row or column of $M$, respectively. We also establish necessary and sufficient conditions that ensure that the resulting array is symmetric with respect to the main diagonal and that each symbol occurs at least a prescribed number of times on the main diagonal. These results generalize Ryser’s theorem for Latin rectangles and Andersen and Hoffman’s independent theorems for symmetric Latin rectangles with prescribed diagonal tails. Second, let $G$ be a loopless multi-graph. The edge-chromatic index $\chi'(G)$ is the smallest integer $k$ such that there exists a proper coloring of the edges of $G$ with $k$ colors. In the 1960s, Vizing and Gupta independently proved that $\chi'(G)\leq \mu(G) + \Delta(G)$. In 2000, Steffen refined this bound by taking into consideration the girth $g(G)$ of a graph $G$, the length of a shortest cycle in the underlying simple graph of $G$. His result established that $\chi'(G) \leq \Delta(G) + \roundup{\mu(G)/\rounddown{g(G)/2}}$. A ring graph is a graph whose underlying simple graph is a cycle. We show that any critical graph with $\mu(G)\geq g(G)\geq 5$ which achieves Steffen's bound is a ring graph of odd girth, partially answering two problems posed by Stiebitz et al.