2021/04/30 by Yixin Cao, Cao, Yixin, Shenghua Wang +1
Computer Science · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2104.14935
Inspired by applications of perfect graphs in combinatorial optimization, Chvátal defined t-perfect graphs in 1970s. The long efforts of characterizing t-perfect graphs started immediately, but embarrassingly, even a working conjecture on it is still missing after nearly 50 years. Unlike perfect graphs, t-perfect graphs are not closed under substitution or complementation. A full characterization of t-perfection with respect to substitution has been obtained by Benchetrit in his Ph.D. thesis. Through the present work 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 minimally t-imperfect.