×

A class of \(\beta\)-perfect graphs. (English) Zbl 0952.05028

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)].

MSC:

05C17 Perfect graphs
PDFBibTeX XMLCite
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.