On Fork-free T-perfect Graphs
share
In an attempt to understanding the complexity of the independent set problem, Chvátal defined t-perfect graphs. While a full characterization of this class is still at large, progress has been achieved for claw-free graphs [Bruhn and Stein, Math. Program. 2012] and P_5-free graphs [Bruhn and Fuchs, SIAM J. Discrete Math. 2017]. We take one more step to characterize fork-free t-perfect graphs, and show that they are strongly t-perfect and three-colorable. We also present polynomial-time algorithms for recognizing and coloring these graphs.
READ FULL TEXT
