A Hereditary Generalization of the Nordhaus-Gaddum Graphs (Rebecca Whitman)
- Series
- Graph Theory Seminar
- Time
- Tuesday, November 12, 2024 - 15:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Rebecca Whitman – University of California Berkeley
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.