On circular critical graphs (Q796546): Difference between revisions

A graph is called circular if its automorphism group contains an n-cycle. A graph G is perfect if for all vertex-induced subgraphs H, the size of the largest clique in H equals the size of the minimal coloring of H. The Strong Perfect Graph Conjecture states that a graph is perfect if and only if the graph does not contain an odd-length chordless circuit (of length \(\geq 5)\) or the complement of such a circuit. Such circuits and their complements are trivially circular graphs. A graph is critical perfect if it is not perfect but all proper vertex-induced subgraphs are perfect. This paper examines circular graphs that are close in structure to critical perfect graphs and obtains evidence supporting the Strong Perfect Graph Conjecture.