Problem of the Week
Hilton Memorial Lecture
We explore the new concept of deficiency in signed graphs. The deficiency of a signed graph coloration is the number of unused colors from the color set. We introduce deficiency, switching deficiency, and related concepts. We show one important use of deficiency in proving a chromatic number theorem about signed graph joins. We then present results on the switching deficiency for all signed graphs, the deficiency for 2-chromatic graphs, and the deficiency for several families of 3-chromatic graphs. The main chapter contains a polynomial-time algorithm for deciding the maximum deficiency of a 3-chromatic signed graph. We end with limited results on the minimum deficiency of 3-chromatic signed graphs and ideas for further research.
This is Ms. Cyr's doctoral dissertation defense. The examining committee consists of Laura Anderson, Michael Dobbins, Leslie Lander (outside examiner), and Thomas Zaslavsky (chair).
All are welcome to participate via Zoom.