User Tools

Site Tools


Richard Behr (Binghamton)

Signed Graph Coloring

Abstract for the Combinatorics Seminar 2016 March 22

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.

Brooks' Theorem for Signed Graphs

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.

The Chromatic Polynomial of a Signed Graph

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

seminars/comb/abstract.201603beh.txt · Last modified: 2020/01/29 14:03 (external edit)