UC Berkeley

A graph G = (V (G), E(G)) is an ordered pair consisting of a finite vertex set V (G) and an edge set E(G) of unordered pairs of distinct vertices. Given a graph G, a graph H is an induced subgraph of G if V (H) ⊆ V (G) and E(H) is exactly the set of edges among V (H) inherited from G. A class A of graphs is hereditary if A contains all induced subgraphs of graphs in A. Hereditary classes are particularly interesting because each can be characterized by a set of forbidden induced subgraphs. Where a class A is not hereditary, we define the hereditary subclass of A to be the largest hereditary class contained within A, and the hereditary closure to be the smallest hereditary class containing A. In this dissertation, I study the hereditary subclasses and closures of important non-hereditary graph classes, defined by relationships among invariants.Given a graph, we can color its vertices such that no two adjacent vertices are the same color. If such a coloring exists with k colors, we call G k-colorable. The chromatic number χ(G) is the minimum number k such that G is k-colorable. Computing χ(G) generally is NP-complete, as is evaluating whether G is k-colorable for k ≥ 3. The sum and product of the chromatic number of a graph G and its complement G are both bounded in terms of |V (G)|. The families of graphs satisfying each of these inequalities with equality are known, but little is known about how far a given graph is from meeting either the lower or upper bounds with equality.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 dissertation I consider a hereditary generalization: graphs G for which all induced subgraphs H of G satisfy χ(H) + χ(H) ≥ |H|. I characterize the forbidden induced subgraphs of this class and find its intersection with a number of common classes, including line graphs. I also discuss χ-boundedness and algorithmic results.I then generalize further: for a fixed constant a, let the a-hereditary-Nordhaus-Gaddum graphs be those satisfying χ(G) + ω(G) ≥ |G| + 1 − a for all induced subgraphs. I bring to light a substantive connection between polyominoes and graph coloring, furthering the early work of Finck. Using polyominoes, for both the a-hereditary-Nordhaus-Gaddum graphs and a generalization of sum-perfect graphs, I show that there are finitely many forbidden induced subgraphs, resolving a question of Litjens, Polak, and Sivaraman, and provide a minimum and upper bound on their order. I provide a partial forbidden induced subgraph characterization of these graph classes. Lastly, I show an equivalence between a-hereditary-Nordhaus-Gaddum graphs, bounded-apex-split graphs, and generalized sum-perfect graphs based on their shared bipartite forbidden induced subgraphs.Another set of problems relate to degree sequences and realizations. In most cases, multiple graphs have the same degree sequence, but a select number of graphs have a unique degree sequence. We say a graph with degree sequence π is a unigraph if it is isomorphic to every graph that has degree sequence π. The class of unigraphs is not hereditary and in this dissertation I study the related hereditary class HCU, the hereditary closure of unigraphs, consisting of all graphs induced in a unigraph. I characterize the class HCU in multiple ways making use of the tools of a decomposition due to Tyshkevich and a partial order on degree sequences due to Rao. I show that all unigraphs are apex-perfect graphs. I also provide a new characterization of the class that consists of unigraphs for which all induced subgraphs are also unigraphs.Given a class A of graphs, I define the class of A-unigraphs to be graphs identifiable from degree sequence and membership in A. While these classes are often not hereditary, I provide characterizations of the largest hereditary subclass contained in the bipartite-unigraphs, the perfect-unigraphs, the forest-unigraphs, the chordal-unigraphs, and the weakly-chordal-unigraphs. I also characterize the largest hereditary subclass contained in the bipartite-unigraphs in terms of structure, degree sequence, and a partial order on degree sequences due to Rao.