Herrera de Figueiredo, Celina M.; Vušković, Kristina A class of \(\beta\)-perfect graphs. (English) Zbl 0952.05028 Discrete Math. 216, No. 1-3, 169-193 (2000). The chromatic number of a graph \(G\) is denoted by \(\chi(G)\), and the minimum degree of \(G\) by \(\delta_G\). A well-known upper bound for \(\chi(G)\) is \(\beta(G):=\max\{1+\delta_{G'} \mid G'\) induced subgraph of \(G\}\). Due to S. E. Markossian, G. S. Gasparian, and B. A. Reed [\(\beta\)-perfect graphs, J. Comb. Theory, Ser. B 67, No. 1, 1-11 (1996; Zbl 0857.05038)], a graph \(G\) is called \(\beta\)-perfect if, for each induced subgraph \(H\) of \(G\), \(\chi(H)=\beta(H)\). A short-chorded cycle is a cycle with exactly one chord that forms a triangle with two edges of the cycle. Markossian et al. proved that graphs containing no chordless cycle of even length and no short-chorded cycle of even length are \(\beta\)-perfect. The authors improve this result by showing that graphs containing no chordless cycle of even length, no short-chorded cycle on four or six vertices are \(\beta\)-perfect. This new class of \(\beta\)-perfect graphs can be recognized in polynomial time because testing whether a graph contains a chordless cycle of even length can be done efficiently, as shown by M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković [Even and odd holes in cap-free graphs, J. Graph Theory 30, No. 4, 289-308 (1999; Zbl 0920.05028)]. Reviewer: Van Bang Le (Rostock) Cited in 3 Documents MSC: 05C17 Perfect graphs Keywords:perfect graphs; \(\beta\)-perfect graphs; even holes; chromatic number Citations:Zbl 0920.05028; Zbl 0857.05038 PDFBibTeX XMLCite \textit{C. M. Herrera de Figueiredo} and \textit{K. Vušković}, Discrete Math. 216, No. 1--3, 169--193 (2000; Zbl 0952.05028) Full Text: DOI References: [1] M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, Even-hole-free graphs, Part I: decomposition theorem and Part II: recognition algorithm, preprint, 1997, J. Graph Theory, submitted for publication.; M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, Even-hole-free graphs, Part I: decomposition theorem and Part II: recognition algorithm, preprint, 1997, J. Graph Theory, submitted for publication. [2] M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, Finding an even hole in a graph, Proceedings of the 38th Annual Conference on Foundations of Computer Science, 1997, pp. 480-485.; M. Conforti, G. Cornuéjols, A. Kapoor, K. Vušković, Finding an even hole in a graph, Proceedings of the 38th Annual Conference on Foundations of Computer Science, 1997, pp. 480-485. [3] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703 [4] Markossian, S. E.; Gasparian, G. S.; Reed, B. A., \(β\)-perfect graphs, J. Combin. Theory Ser. B, 67, 1-11 (1996) · Zbl 0857.05038 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.