Back to Search
Start Over
On circular-perfect graphs: A survey.
- Source :
-
European Journal of Combinatorics . Jan2021, Vol. 91, pN.PAG-N.PAG. 1p. - Publication Year :
- 2021
-
Abstract
- Circular-perfect graphs form a natural superclass of perfect graphs, introduced by Zhu almost 20 years ago: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ -bound graphs with the smallest non-trivial χ -binding function χ (G) ≤ ω (G) + 1. In this paper, we survey the results about circular-perfect graphs obtained in the two last decades, with a focus on whether the fascinating properties of perfect graphs can be extended to this superclass. We recall the deep algorithmic properties of perfect graphs and the underlying polyhedral graph theory, in order to outline in this setting the main graph parameters that are also related to circular-perfect graphs. Finally, we give a list of open problems. [ABSTRACT FROM AUTHOR]
- Subjects :
- *NONLINEAR functions
*GRAPH theory
*POLYHEDRAL functions
*DEFINITIONS
Subjects
Details
- Language :
- English
- ISSN :
- 01956698
- Volume :
- 91
- Database :
- Academic Search Index
- Journal :
- European Journal of Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 146413017
- Full Text :
- https://doi.org/10.1016/j.ejc.2020.103224