



3Colourability

Linear 
[+]Details 


Linear from Colourability Linear from Cliquewidth expression Polynomial from Cliquewidth expression Polynomial from Colourability
Linear on dually chordal
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 circular arc
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 2track
Polynomial on B_{0}VPG
Polynomial on biclique separable
Polynomial [$O(V \log V)$]
on boxicity 2
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

Linear 
[+]Details 


Polynomial from Colourability on the complement Polynomial from Cliquewidth expression
Linear on circular arc
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 probe ptolemaic
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
Linear on chordal
Polynomial on P_{4}free
Polynomial on βperfect
Polynomial on biclique separable
Polynomial [$O(V^2)$]
on chordal
Polynomial on circular perfect
Polynomial on clique separable
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 [$O(V \log V)$]
on permutation
Polynomial 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 circular arc
Linear on distancehereditary
Linear on dually chordal
Linear on interval
Linear [$O(V)$]
on permutation
Polynomial on ATfree
Polynomial [$O(n^2 log^5 n)$]
on cobounded tolerance
Polynomial on cocomparability
Polynomial on cointerval ∪ interval
Polynomial on cograph
Polynomial on directed path
Polynomial on kpolygon
Polynomial on permutation
Polynomial on probe interval
Polynomial on strongly chordal
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 on chordal
Polynomial on circular arc
Polynomial [$O(V^4)$]
on cocomparability
Polynomial [$O(V^2E)$]
on cocomparability
Polynomial on interval
Polynomial [$O(VE)$]
on permutation
Polynomial [$O(V^6)$]
on permutation
Polynomial [$O(VE^2)$]
on permutation
Polynomial [$O(VE)$]
on trapezoid

Graph isomorphism

Linear 
[+]Details 


Linear on interval
Linear on permutation
Polynomial on cointerval ∪ interval
Polynomial on cograph

Hamiltonian cycle

Linear 
[+]Details 


Polynomial from Cliquewidth expression
Linear on cograph
Linear on distancehereditary
Linear on interval
Polynomial [$O(V^2 \log V)$]
on circular arc
Polynomial [$O(V \Delta(G))$]
on circular arc
Polynomial on cocomparability
Polynomial [$O(V \log V)$]
on interval

Hamiltonian path

Linear 
[+]Details 


Polynomial from Cliquewidth expression
Linear on cograph
Linear on distancehereditary
Polynomial [$O(V^4)$]
on circular arc
Polynomial on cocomparability
Polynomial [$O(V \log V)$]
on interval

Independent dominating set

Linear 
[+]Details 


Linear from Weighted independent dominating set Polynomial from Weighted independent dominating set
Linear on chordal

Independent set

Linear 
[+]Details 


Linear from Weighted independent set Polynomial from Clique on the complement Polynomial from Weighted independent set
Linear on P_{4}tidy
Linear on chordal
Linear [$O(n)$]
on circular arc
Linear on cocomparability
Linear on extended P_{4}laden
Linear on partnerlimited
Polynomial on (C_{4},P_{6})free
Polynomial on (C_{5},P_{5},P_{2} ∪ P_{3})free
Polynomial on (C_{6},K_{3,3}+e,P,P_{7},X_{37},X_{41})free
Polynomial on (E,P)free
Polynomial on EPT
Polynomial on Gallai
Polynomial on (K_{2,3},P,P_{5})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 on (P_{5},P_{2} ∪ P_{3})free
Polynomial [$O(V min(d,\alpha))$]
on circle
Polynomial on clique separable
Polynomial on cobiclique separable
Polynomial on comparability
Polynomial [$O(VE)$]
on weakly chordal

Maximum cut

Polynomial 
[+]Details 


Polynomial [$O(V^2)$]
on cograph

Recognition

Linear 
[+]Details 


Linear on quasithreshold
Polynomial on (C_{4},P_{4})free

Treewidth

Linear 
[+]Details 


Linear on distancehereditary
Linear on permutation
Polynomial on HHDfree
Polynomial on chordal
Polynomial on circle
Polynomial on circular arc
Polynomial on circular permutation
Polynomial on cocomparability graphs of dimension d posets
Polynomial on cograph
Polynomial on dtrapezoid
Polynomial on dtrapezoid
Polynomial on interval
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 [$O(V^2 E)$]
on C_{4}free ∩ oddsignable
Polynomial on alternation
Polynomial [$O(V^2 + E \log \log V)$]
on circle
Polynomial [$O(V^2 \log V)$]
on circletrapezoid
Polynomial [$O(VE)$]
on circular arc
Polynomial on cocomparability ∪ comparability
Polynomial on interval filament
Polynomial on maxtolerance
Polynomial on maximal clique irreducible
Polynomial [$O(VE)$]
on perfectly orderable
Polynomial [$O(VE)$]
on splitneighbourhood
Polynomial [$O(V log log V)$]
on trapezoid

Weighted feedback vertex set

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Cliquewidth expression
Linear on interval
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
Polynomial on strongly chordal

Weighted independent set

Linear 
[+]Details 


Linear from Cliquewidth expression Polynomial from Weighted clique on the complement Polynomial from Cliquewidth expression
Linear on (P_{5},gem)free
Linear on chordal
Linear on distancehereditary
Linear on permutation
Polynomial [$O(V + V \Delta(G))$]
on 2thin
Polynomial [$O(V^4)$]
on ATfree
Polynomial [$O(V^5E^3)$]
on Berge ∩ bullfree
Polynomial on (C_{4},C_{5},T_{2})free
Polynomial [$O(n^4)$]
on (C_{4},P_{5})free
Polynomial on (C_{4},P_{6})free
Polynomial on (K_{2,3},P,P_{5})free
Polynomial on (K_{2,3},P,hole)free
Polynomial on (K_{2,3},P_{5})free
Polynomial [$O(n^6)$]
on (K_{3,3},P_{5})free
Polynomial [$O(n^8)$]
on (K_{4,4},P_{5})free
Polynomial on (P,P_{5},3K_{2},gem)free
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(ln)$]
on circular arc
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
