Hereditary Nordhaus-Gaddum Graphs
read the original abstract
Nordhaus and Gaddum proved in 1956 that the sum of the chromatic number $\chi$ 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 $\chi(H) + \chi(\overline{H}) \le |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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Mechanistic origins of catastrophic forgetting: why RL preserves circuits better than SFT?
RL preserves a larger fraction of base model circuits than SFT during fine-tuning on scientific QA, per a new head-level differential circuit vulnerability metric, at the cost of slower adaptation.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.