2023/10/03 by Vaidy Sivaraman, Sivaraman, Vaidy, Rebecca Whitman +1
Computer Science · Engineering · #05C17 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2310.02336
openalex publication_date 2023/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 χ(H) + χ(H) ≤ |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 χ-boundedness and algorithmic results.