A signed graph is a graph where each edge is assigned either a positive or negative sign. Many concepts from the theory of ordinary (unsigned) graphs generalize nicely to signed graphs. One such concept is that of vertex coloring. A k-coloring of a signed graph is an assignment of an integer between −k and k (a “signed color”) to each of its vertices. The signed colors and signed edges interact nicely together and provide a theory of coloring that specializes to ordinary coloring of unsigned graphs when all edges are positive.

In the first of two talks I will give an introduction to signed graphs and their colorings, culminating in a proof of a signed version of Brooks' Theorem for chromatic number that generalizes the classical unsigned theorem. This talk is based on the new paper “The chromatic number of a signed graph” by Edita Máčajová, André Raspaud, and Martin Škoviera.

In the second talk I will introduce the chromatic polynomial of a signed graph and prove some of the important properties it possesses. This talk is based on the old papers “Signed graph coloring” and “Chromatic invariants of signed graphs” by Thomas Zaslavsky.

These two talks constitute Mr. Behr's Admission-to-Candidacy examination. The examining committee consists of Michael Dobbins, Fernando Guzmán, and Thomas Zaslavsky (chair).