- Series
- Graph Theory Seminar
- Time
- Tuesday, November 12, 2024 - 3:30pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Rebecca Whitman – University of California Berkeley – https://math.berkeley.edu/people/grad/rebecca-whitman
- Organizer
- Evelyne Smith-Roberge
Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number of a graph G and its complement is at most |G|+1. The Nordhaus-Gaddum graphs are the class of graphs satisfying this inequality with equality, and are well-understood. In this paper we consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy that the sum of the chromatic numbers of H and its complement are at least |H|. We characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. We also discuss chi-boundedness and algorithmic results.