Graphs Identifiable by Degree Sequence and Chromatic Number

Unigraphs are graphs identifiable up to isomorphism from their degree sequences. Given a class A of graphs, we define the class of A-unigraphs to be graphs identifiable from degree sequence and membership in A. While these classes are often not hereditary, we provide characterizations of the largest hereditary subclass contained in the bipartite-unigraphs, the k-partite unigraphs, the perfect-unigraphs, and the chordal-unigraphs. We 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. Lastly, we show that all unigraphs G satisfy the bound (G) (G) + 1 and are hence apex-perfect graphs.