====== Richard Behr (Binghamton) ======

====== Edge Coloring and Special Edges of Signed Graphs ======

===== Abstract for the Combinatorics Seminar 2018 April 17 =====

My dissertation concerns signed graphs—graphs that have either a plus or minus sign assigned to each of their edges. I discuss two different, unrelated topics.

First, I define a method for edge coloring signed graphs and what it means for such a coloring to be proper. My method has many desirable properties: it specializes to the usual notion of edge coloring when the signed graph is all negative, it has a natural definition in terms of vertex coloring of a line graph, and the maximum number of colors required for a proper coloring of a signed simple graph is bounded above by Δ+1, in parallel with Vizing's Theorem for ordinary graphs. In fact, Vizing's Theorem is a special case of the more difficult theorem concerning signed graphs. I also prove a signed version of Shannon's theorem, bounding the number of colors needed to edge color a certain type of signed multigraph. I discuss other related topics, such as methods for defining total coloring for signed graphs, and the relationship between signed edge coloring and the Linear Arboricity Conjecture.

Second, I examine the conditions under which a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle. For an edge in a unique signed circle, the positive and negative cases require the same structure of the underlying graph, but the requirements of the signature are different. I characterize the necessary structure of the underlying graph in terms of bridges of a circle. I then use the results from the edge version of the problem to solve the vertex version.

(This talk is part of Mr. Behr's doctoral dissertation defense. The examining committee consists of Michael Dobbins, Fernando Guzmán, Leslie Lander, and Thomas Zaslavsky (chair).)


----