A graph is perfect if for all induced subgraphs H: \chi(H) = \omega(H), where \chi is the chromatic number and \omega is the size of a maximum clique.
;
selfcomplementary
The map shows the inclusions between the current class and a fixed set of landmark classes. Minimal/maximal is with respect to the contents of ISGCI. Only references for direct inclusions are given. Where no reference is given, check equivalent classes or use the Java application. To check relations other than inclusion (e.g. disjointness) use the Java application, as well.
Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.
3Colourability
[?]

Polynomial  [+]Details  
Clique
[?]

Polynomial  [+]Details  
Clique cover
[?]

Polynomial  [+]Details  
Cliquewidth
[?]
Whether the cliquewidth of the graphs in this class is bounded by a
constant k
.
The cliquewidth of a graph is the number of different labels that is needed to construct the graph using the following operations:

Unbounded  [+]Details  
Cliquewidth expression
[?]

Unbounded or NPcomplete  [+]Details  
Colourability
[?]

Polynomial  [+]Details  
Cutwidth
[?]

NPcomplete  [+]Details  
Domination
[?]

NPcomplete  [+]Details  
Feedback vertex set
[?]

NPcomplete  [+]Details  
Graph isomorphism
[?]

GIcomplete  [+]Details  
Hamiltonian cycle
[?]

NPcomplete  [+]Details  
Hamiltonian path
[?]

NPcomplete  [+]Details  
Independent dominating set
[?]

NPcomplete  [+]Details  
Independent set
[?]

Polynomial  [+]Details  
Maximum cut
[?]
(decision variant)

NPcomplete  [+]Details  
Recognition
[?]

Polynomial  [+]Details  
Treewidth
[?]

NPcomplete  [+]Details  
Weighted clique
[?]

Polynomial  [+]Details  
Weighted feedback vertex set
[?]

NPcomplete  [+]Details  
Weighted independent dominating set
[?]

NPcomplete  [+]Details  
Weighted independent set
[?]

Polynomial  [+]Details  
Weighted maximum cut
[?]
(decision variant)

NPcomplete  [+]Details 