On circular critical graphs (Q796546): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Q686171 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Alan C. Tucker / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4070781 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial designs related to the strong perfect graph conjecture / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3236733 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A characterization of perfect graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Perfect zero–one matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coloring a Family of Circular Arcs / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0012-365x(84)90019-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2066125721 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:53, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On circular critical graphs |
scientific article |
Statements
On circular critical graphs (English)
0 references
1984
0 references
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.
0 references
circular graph
0 references
perfect graph
0 references
critical perfect graphs
0 references