



3Colourability

Linear 
[+]Details 


Linear from Colourability Linear from Cliquewidth expression Polynomial from Cliquewidth expression Polynomial from Colourability
Polynomial [$O(V^4)$]
on ATfree
Polynomial on P_{2} ∪ P_{4}free
Polynomial on P_{5}free
Polynomial on P_{6}free
Polynomial on circle
Polynomial on cogemfree

Clique

Linear 
[+]Details 


Linear from Weighted clique Polynomial from Independent set on the complement Polynomial from Weighted clique
Linear on Matula perfect
Linear on WelshPowell perfect
Polynomial on biclique separable
Polynomial [$O(V log^2 V)$]
on circle
Polynomial on circular perfect
Polynomial [$O(V \log V)$]
on multitolerance
Polynomial [$O(V \log V)$]
on tolerance

Clique cover

Polynomial 
[+]Details 


Polynomial from Colourability on the complement Polynomial from Cliquewidth expression
Polynomial [$O(V log^{d1} V)$]
on dtrapezoid
Polynomial [$O(V log log V)$]
on trapezoid

Cliquewidth

Bounded 
[+]Details 


Bounded from Cliquewidth on the complement
Bounded on (5,1)
Bounded on (6,2)
Bounded on (7,3)
Bounded on (9,6)
Bounded on (P,P,cofork,fork)free
Bounded on (P_{5},bull,house)free
Bounded on (P_{5},fork,house)free
Bounded on (P_{5},gem)free
Bounded on (P,fork,gem)free
Bounded on (P,fork,house)free
Bounded on (bull,cofork,fork)free
Bounded on (bull,fork,gem)free
Bounded on (bull,fork,house)free
Bounded on cliquewidth 2
Bounded on cliquewidth 3
Bounded on cliquewidth 4
Bounded on (cogem,gem)free
Bounded on distancehereditary
Bounded on partnerlimited
Bounded on probe P_{4}reducible
Bounded on probe P_{4}sparse
Bounded on probe distancehereditary
Bounded on (q, q3), fixed q>= 7
Bounded on (q,q4), fixed q
Bounded on semiP_{4}sparse
Bounded on treecograph

Cliquewidth expression

Linear 
[+]Details 


Polynomial from Cliquewidth expression on the complement Polynomial from Cliquewidth
Linear on (5,1)
Linear on (6,2)
Linear on (7,3)
Linear on (9,6)
Linear on (P,P,cofork,fork)free
Linear on P_{4}tidy
Linear on P_{4}tidy
Linear on (P_{5},bull,house)free
Linear on (P_{5},fork,house)free
Linear on (P,fork,gem)free
Linear on (P,fork,house)free
Linear on (bull,cofork,fork)free
Linear on (bull,fork,gem)free
Linear on (bull,fork,house)free
Linear on cliquewidth 2
Linear on distancehereditary
Linear on partnerlimited
Linear on (q, q3), fixed q>= 7
Linear on (q,q4), fixed q
Linear on semiP_{4}sparse
Polynomial [$O(V^2E)$]
on cliquewidth 3
Polynomial on treecograph

Colourability

Linear 
[+]Details 


Polynomial from Clique cover on the complement Polynomial from Cliquewidth expression
Linear on Matula perfect
Linear on WelshPowell perfect
Polynomial on P_{4}free
Polynomial on biclique separable
Polynomial on circular perfect
Polynomial [$O(V^3)$]
on cocomparability
Polynomial [$O(V^2)$]
on comparability
Polynomial [$O(V \log V)$]
on multitolerance
Polynomial on perfect
Polynomial [$O(VE)$]
on perfectly orderable
Polynomial on permutation
Polynomial [$O(V \log V)$]
on permutation
Polynomial [$O(V \log V)$]
on tolerance
Polynomial [$O(V log log V)$]
on trapezoid
Polynomial [$O(V^4E)$]
on weakly chordal

Cutwidth

Unknown to ISGCI 
[+]Details 



Domination

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression
Linear on distancehereditary
Linear [$O(V)$]
on permutation
Polynomial on ATfree
Polynomial [$O(n^2 log^5 n)$]
on cobounded tolerance
Polynomial on cocomparability
Polynomial
Polynomial on kpolygon
Polynomial on permutation
Polynomial on trapezoid

Feedback vertex set

Linear 
[+]Details 


Linear from Weighted feedback vertex set Polynomial from Weighted feedback vertex set
Polynomial [$O(V^8E^2)$]
on ATfree
Polynomial [$O(V^4)$]
on cocomparability
Polynomial [$O(V^2E)$]
on cocomparability
Polynomial [$O(VE^2)$]
on permutation
Polynomial [$O(V^6)$]
on permutation
Polynomial [$O(VE)$]
on permutation
Polynomial [$O(VE)$]
on trapezoid

Hamiltonian cycle

Linear 
[+]Details 


Polynomial from Cliquewidth expression
Linear
Linear on distancehereditary
Polynomial on cocomparability

Hamiltonian path

Linear 
[+]Details 


Polynomial from Cliquewidth expression
Linear
Linear on distancehereditary
Polynomial on cocomparability

Independent dominating set

Linear 
[+]Details 


Linear from Weighted independent dominating set Polynomial from Weighted independent dominating set

Independent set

Linear 
[+]Details 


Linear from Weighted independent set Polynomial from Weighted independent set Polynomial from Clique on the complement
Linear on P_{4}tidy
Linear on cocomparability
Linear on extended P_{4}laden
Linear on partnerlimited
Polynomial on (E,P)free
Polynomial [$O(nm)$]
on (K_{3,3}e,P_{5},X_{98})free
Polynomial [$O(V^{5})$]
on (K_{3,3}e,P_{5},X_{99})free
Polynomial on (K_{3,3}e,P_{5})free
Polynomial on Meyniel
Polynomial [$O(VE)$]
on (P,P_{5})free
Polynomial [$O(V^8)$]
on (P,P_{7})free
Polynomial on (P,P_{8})free
Polynomial on (P,T_{2})free
Polynomial on (P,star_{1,2,5})free
Polynomial [$O(V min(d,\alpha))$]
on circle
Polynomial on cobiclique separable
Polynomial on comparability
Polynomial [$O(VE)$]
on weakly chordal

Maximum cut

Polynomial 
[+]Details 


Polynomial [$O(V^2)$]

Recognition

Linear 
[+]Details 


Linear
Linear
Polynomial on P_{4}free

Treewidth

Linear 
[+]Details 


Linear on distancehereditary
Linear on permutation
Polynomial on HHDfree
Polynomial on circle
Polynomial on circular permutation
Polynomial on cocomparability graphs of dimension d posets
Polynomial
Polynomial on dtrapezoid
Polynomial on dtrapezoid
Polynomial on permutation
Polynomial on (q,q4), fixed q
Polynomial [$O(V^2)$]
on trapezoid
Polynomial [$O((V+E) \log V)$]
on weak bipolarizable
Polynomial on weakly chordal

Weighted clique

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression Polynomial from Weighted independent set on the complement
Linear on comparability
Polynomial on alternation
Polynomial [$O(V^2 + E \log \log V)$]
on circle
Polynomial [$O(V^2 \log V)$]
on circletrapezoid
Polynomial on cocomparability ∪ comparability
Polynomial on interval filament
Polynomial [$O(VE)$]
on perfectly orderable
Polynomial [$O(V log log V)$]
on trapezoid

Weighted feedback vertex set

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression
Polynomial on circle
Polynomial [$O(V^{2n+5})$]
on circlengon, fixed n

Weighted independent dominating set

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression

Weighted independent set

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression Polynomial from Weighted clique on the complement
Linear on (P_{5},gem)free
Linear on distancehereditary
Linear on permutation
Polynomial [$O(V^4)$]
on ATfree
Polynomial [$O(V^5E^3)$]
on Berge ∩ bullfree
Polynomial on (P,P_{5})free
Polynomial [$O(V^9 E)$]
on (P,P_{7})free
Polynomial on (P_{5},X_{82},X_{83})free
Polynomial on (P_{5},cofork)free
Polynomial [$O(VE)$]
on (P_{5},fork)free
Polynomial on (P_{5},house)free
Polynomial on P_{5}free
Polynomial [$O(VE)$]
on (P,fork)free
Polynomial [$O(VE)$]
on (bull,fork)free
Polynomial [$O(V^2)$]
on circle
Polynomial [$O(V^2)$]
on circletrapezoid
Polynomial [$O(V^2 \log \log V)$]
on circular trapezoid
Polynomial on (cofork,hole)free
Polynomial [$O(VE)$]
on cogemfree
Polynomial [$O(V log^{d1} V)$]
on dtrapezoid
Polynomial on forkfree
Polynomial on interval filament
Polynomial [$O(E + V \log V)$]
on multitolerance
Polynomial on (n+4)panfree
Polynomial on parity
Polynomial on perfect
Polynomial on semiP_{4}sparse
Polynomial on subtree overlap
Polynomial [$O(V^2)$]
on tolerance
Polynomial [$O(V \log V)$]
on tolerance
Polynomial [$O(V \log \log V)$]
on trapezoid
Polynomial [$O(V^4)$]
on weakly chordal

Weighted maximum cut

NPcomplete 
[+]Details 


NPcomplete on 2K_{1}free
NPcomplete on P_{3}free
