On Fork‐Free t‐Perfect Graphs

ABSTRACT In an effort to understand the complexity of the maximum independent set problem, Chvátal introduced t‐perfect graphs. While a full characterization of this class remains open, important progress has been made for claw‐free graphs [Bruhn and Stein, Math. Program. 2012] and ‐free graphs [Bruhn and Fuchs, SIAM J. Discrete Math. 2017]. We take a further step by characterizing fork‐free t‐perfect graphs and showing that they are strongly t‐perfect and 3‐colorable. We also give polynomial‐time algorithms for recognizing and coloring fork‐free t‐perfect graphs.