Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/119339
| Title: | On fork-free t-perfect graphs | Authors: | Cao, Y Wang, S |
Issue Date: | 2026 | Source: | Journal of graph theory, First published: 13 June 2026, Early View, https://doi.org/10.1002/jgt.70085 | 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 P5-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. | Publisher: | John Wiley & Sons, Inc. | Journal: | Journal of graph theory | ISSN: | 0364-9024 | EISSN: | 1097-0118 | DOI: | 10.1002/jgt.70085 | Rights: | This is an open access article under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits use, distribution and reproduction in any medium, provided the original work is properly cited. © 2026 The Author(s). Journal of Graph Theory published by Wiley Periodicals LLC. The following publication Y. Cao, and S. Wang, “On Fork-Free t-Perfect Graphs,” Journal of Graph Theory, 0 (2026): 1-18 is available at https://doi.org/10.1002/jgt.70085. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Cao_Fork‐Free_t‐Perfect_Graphs.pdf | 2.34 MB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.