Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/119339
PIRA download icon_1.1View/Download Full Text
DC FieldValueLanguage
dc.contributorDepartment of Computingen_US
dc.creatorCao, Yen_US
dc.creatorWang, Sen_US
dc.date.accessioned2026-06-16T02:49:48Z-
dc.date.available2026-06-16T02:49:48Z-
dc.identifier.issn0364-9024en_US
dc.identifier.urihttp://hdl.handle.net/10397/119339-
dc.language.isoenen_US
dc.publisherJohn Wiley & Sons, Inc.en_US
dc.rightsThis 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.en_US
dc.rights© 2026 The Author(s). Journal of Graph Theory published by Wiley Periodicals LLC.en_US
dc.rightsThe 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.en_US
dc.titleOn fork-free t-perfect graphsen_US
dc.typeJournal/Magazine Articleen_US
dc.identifier.doi10.1002/jgt.70085en_US
dcterms.abstractIn 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.en_US
dcterms.accessRightsopen accessen_US
dcterms.bibliographicCitationJournal of graph theory, First published: 13 June 2026, Early View, https://doi.org/10.1002/jgt.70085en_US
dcterms.isPartOfJournal of graph theoryen_US
dcterms.issued2026-
dc.identifier.eissn1097-0118en_US
dc.description.validate202606 bcchen_US
dc.description.oaVersion of Recorden_US
dc.identifier.FolderNumbera4517-
dc.identifier.SubFormID53021-
dc.description.fundingSourceRGCen_US
dc.description.fundingSourceOthersen_US
dc.description.fundingTextFunding: National Natural Science Foundation of China (NSFC), Grant/Award Number: 62372394; Hong Kong Research Grants Council(RGC), Grant/Award Number: 15221420en_US
dc.description.pubStatusEarly releaseen_US
dc.description.oaCategoryCCen_US
Appears in Collections:Journal/Magazine Article
Files in This Item:
File Description SizeFormat 
Cao_Fork‐Free_t‐Perfect_Graphs.pdf2.34 MBAdobe PDFView/Open
Open Access Information
Status open access
File Version Version of Record
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.