Critical (P6, banner)-free graphs

作     者：Huang, Shenwei Li, Tao Shi, Yongtang 

作者机构：Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2019年第258卷

页      面：143-151页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Natural Science Foundation of China [11801284, 11771221, 11811540390] National Natural Science Foundation National Key Research and Development Program of China [2018YFB1003405, 2016YFC0400709] Natural Science Foundation of Tianjin [17JCQNJC00300] China-Slovenia bilateral project "Some topics in modern graph theory" [12-6] 

主　　题：Coloring Critical graphs Hereditary classes Strong perfect graph theorem Polynomial-time algorithms 

摘      要：Given two graphs H-1 and H-2, a graph is (H-1, H-2)-free if it contains no induced subgraph isomorphic to H-1 or H-2. Let P-t and C-t be the path and the cycle on t vertices, respectively. A banner is the graph obtained from a C-4 by adding a new vertex and making it adjacent to exactly one vertex of the C-4. In this paper, we show that there are finitely many k-critical (P-6, banner)-free graphs for k = 4 and k = 5. For k = 4, we characterize all such graphs. Our results generalize previous results on k-critical (P-6, C-4)-free graphs for k = 4 and k = 5. (C) 2018 Elsevier B.V. All rights reserved.