A class of \(\beta\)-perfect graphs (Q1567275)

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 \textit{S. E. Markossian, G. S. Gasparian}, and \textit{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 \textit{M. Conforti, G. Cornuéjols, A. Kapoor}, and \textit{K. Vušković} [Even and odd holes in cap-free graphs, J. Graph Theory 30, No. 4, 289-308 (1999; Zbl 0920.05028)].