






















Unigraphs are graphs identifiable up to isomorphism from their degree sequences. Given a class $\mathcal{A}$ of graphs, we define the class of $\mathcal{A}$-unigraphs to be graphs identifiable from degree sequence and membership in $\mathcal{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) \le ω(G) + 1$ and are hence apex-perfect graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。