T-perfect graphs and self-complementary graphs

Abstract

The maximum-weight independent set problem is a fundamental NP-hard prob­lem. To gain a deeper understanding of its complexity, identifying graph classes where the problem can be solved in polynomial time has become a popular research area. Perfect graphs have emerged as one such class, characterized by their independent set polytope being fully described by trivial and clique inequalities. Inspired by the polyhedral characterization of perfect graphs, Chv´atal introduced t-perfect graphs, where the independent set polytope is fully described by trivial, edge, and odd-cycle inequalities. This pivotal characteristic enables the development of polynomial-time algorithms to solve the maximum-weight independent set problem specifically for t-perfect graphs. Given that t-perfect graphs are defined from a polyhedral perspective, a profound understanding of their structure is essential. While a full structural characterization of the class of t-perfect graphs is still at large, substantial advancements have been made for claw-free graphs [Bruhn and Stein, Math. Program. 2012] and P5-free graphs [Bruhn and Fuchs, SIAM J. Discrete Math. 2017]. We take one more step to characterize t-perfect graphs that are fork-free, and show that they are strongly t-perfect and three-colorable. We also present polynomial-time algorithms for recognizing and coloring these graphs. Unlike perfect graphs, t-perfect graphs are not closed under substitution or com­plementation. A full characterization of t-perfection with respect to substitution has been obtained by Benchetrit in his Ph.D. thesis. We attempt to understand t­-perfection with respect to complementation. In particular, we show that there are only five pairs of graphs such that both the graphs and their complements are mini­mally t-imperfect. We also identify all t-perfect graphs that are self-complementary. We conduct a more in-depth study of self-complementary graphs. We study split graphs and pseudo-split graphs whose complements are isomorphic to themselves. These special subclasses of self-complementary graphs are actually the core of self-complementary graphs. Indeed, all realizations of forcibly self-complementary degree sequences are pseudo-split graphs. We also give formulas to calculate the number of self-complementary (pseudo-)split graphs of a given order, and show that Trotignon’s conjecture holds for all self-complementary split graphs.