Document Type
Lecture
Publication Date
11-1-2023
Abstract
We study the class of graphs, all of whose induced subgraphs almost satisfy the Nordhaus-Gaddum inequality. This class is characterized by exactly 52 forbidden induced subgraphs. Relationship with perfect graphs and algorithmic problems will be discussed. This is joint work with Rebecca Whitman (University of California, Berkeley).
Relational Format
presentation
Recommended Citation
Sivaraman, Vaidyanathan, "Hereditary Nordhaus-Gaddum graphs" (2023). Combinatorics Seminar. 14.
https://egrove.olemiss.edu/math_combinatorics/14
COinS
