Domination problem

(0,2)-colorable
(0,3)-colorable
(1,1)-colorable
(1,2)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar
(1,2)-polar ∩ chordal
1-string
(2,2)-colorable
(2,2)-colorable ∩ chordal
(2,2)-interval
2-interval
2-split
2-split ∩ perfect
(2K₂,C₄,C₅)-free
(2K₂,C₄)-free
(2K₂,C₅,T₂)-free
(2K₂,C₅)-free
(2K₂,P₆)-free
(2K₂,house)-free
(2K₂,odd anti-hole)-free
2K₂-free
(2K₃ + e,A,C₅,C₆,E,K_3,3-e,P₆,R,X₁₆₆,X₁₆₇,X₁₆₉,X₁₇₀,X₁₇₁,X₁₇₂,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,X₉₈,A,C₆,E,P₆,R,X₁₆₆,X₁₆₇,X₁₆₉,X₁₇₀,X₁₇₁,X₁₇₂,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,X₉₈,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free
(2K₃ + e,A,C₆,E,K_3,3-e,P₆,R,X₁₆₆,X₁₆₇,X₁₆₉,X₁₇₀,X₁₇₁,X₁₇₂,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,X₉₈,A,C₆,E,P₆,R,X₁₆₆,X₁₆₇,X₁₆₉,X₁₇₀,X₁₇₁,X₁₇₂,X₁₈,X₄₅,X₅,X₅₈,X₈₄,X₉₅,X₉₈,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free
(2K₃ + e,X₉₈,house)-free
(2K₃ + e,X₉₉,house)-free
(2K₃ + e,house)-free
(2K₃,2K₃ + e,A,H,X₄₅,XZ₅,co-domino)-free
(2K₃,2P₃,C₅,C₆,C₇,K_2,3,K₃ ∪ P₃,X₈₄,3K₂,C₄ ∪ P₂,C₆,P₂ ∪ P₄,P₆,X₁₈,X₅,co-antenna,co-domino,co-fish)-free
(2K₃,2P₃,C_n+4,K₃ ∪ P₃)-free
(2K₃,C_n+4)-free
(2K₃,X₄₂,A,H,X₄₅,X₄₆,X₄₇,X₄₈,X₄₉,X₅₀,X₅₁,X₅₂,X₅₃,X₅₄,X₅₅,X₅₆,X₅₇)-free
(2K₃,house)-free
(2K₄,house)-free
(2P₃,3K₂,C₄ ∪ P₂,C₆,K_2,3,P₆,X₁₃₀,X₁₃₂,X₁₃₄,X₁₅₂,X₁₅₃,X₁₅₄,X₁₅₅,X₁₅₆,X₁₅₇,X₁₅₈,X₁₈,X₈₄,X₁₁,X₁₂₇,X₁₂₈,X₁₂₉,X₁₃₁,X₁₃₃,X₁₃₅,X₁₃₆,X₁₃₇,X₁₃₈,X₁₃₉,X₁₄₀,X₁₄₁,X₁₄₂,X₁₄₃,X₁₄₄,X₁₄₅,X₁₄₆,X₁₄₇,X₁₄₈,X₁₄₉,X₁₅₀,X₁₅₁,X₃₀,X₃₅,X₄₆,co-XF₁²ⁿ⁺³,co-XF₆²ⁿ⁺³,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free
2P₃-free
3-DIR
3-DIR contact
3-Helly
3-interval
3-mino
(3K₂,C₄ ∪ P₂,C₅,C₆,K₂ ∪ K₃,K_3,3,K_3,3+e,P₂ ∪ P₄,P₆,X₁₈,X₅,2P₃,C₆,C₇,X₈₄,antenna,domino,fish)-free
(3K₃,C_n+4)-free
(3P₃,C_n+4,P₃ ∪ P₄,P₅,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,A)-free
(3P₃,P₃ ∪ P₄,P₅,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,X₁₈₄,X₁₈₅,X₁₈₆,X₁₈₇,X₁₈₈,X₁₈₉,X₁₉₀,X₁₉₁,X₁₉₂,X₁₉₃,5-pan,A,P₆,co-twin-C₅)-free
3d grid
(4-fan,K_1,4,W₄,W₅,A ∪ K₁,co-fork ∪ K₁,gem ∪ K₁,net ∪ K₁)-free
(5,2)
(5,2)-chordal
(5,2)-odd-chordal
(5,2)-odd-crossing-chordal
(5,2)-odd-noncrossing-chordal
(5-pan,A,P₆,X₁₈₆,3P₃,P₃ ∪ P₄,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,X₁₈₄,X₁₈₅,X₁₈₇,X₁₈₈,X₁₈₉,X₁₉₀,X₁₉₁,X₁₉₂,X₁₉₃,house,twin-C₅)-free
(6,1)-chordal
(6,1)-chordal ∩ bipartite
(6,1)-even-chordal
(6,2)-chordal
(A,C₅,C₆,P₆,domino,house)-free
(A,C₅,P₅,A,house,parachute,parapluie)-free
(A,H,K_3,3,K_3,3-e,X₄₅,XZ₅,domino)-free
(A,H,K_3,3,X₄₅,X₄₆,X₄₇,X₄₈,X₄₉,X₅₀,X₅₁,X₅₂,X₅₃,X₅₄,X₅₅,X₅₆,X₅₇,X₄₂)-free
(A,H,K_3,3,X₄₅,triangle)-free
(A,P₆,domino)-free
(A,3P₃,C_n+4,P₃ ∪ P₄,X₁₀₂,X₁₈₀,X₁₈₁,X₁₈₂,X₁₈₃,house)-free
(BW₃,W₅,W₇,X₁₀₃,X₁₀₄,X₁₀₅,X₁₀₆,X₁₀₇,X₁₀₈,X₁₀₉,X₁₁₀,X₁₁₁,X₁₁₂,X₁₁₃,X₁₁₄,X₁₁₅,X₁₁₆,X₁₁₇,X₁₁₈,X₁₁₉,X₁₂₀,X₁₂₁,X₁₂₂,X₁₂₃,X₁₂₄,X₁₂₅,X₁₂₆,X₅₃,X₈₈,C₆,C₈,T₂,X₃)-free
BW₃-free
BW₃-free ∩ modular
Berge
Berge ∩ bull-free
Bouchet
(C₄,C₅,T₂)-free
(C₄,C₅)-free
(C₄,C₅)-free ∩ cop-win
(C₄,P₅)-free
(C₄,P₆)-free
(C₄,odd-hole)-free
C₄-free
(C₅,C₆,P₆,X₁₇,X₁₈,X₅,X₉₈,C₆,P₆,antenna,domino)-free
(C₅,C₆,P₆,C₆,P₆,X₁₇,X₁₈,X₅,X₉₈,co-antenna,co-domino)-free
(C₅,C₆,P₆,C₆,P₆)-free
(C₅,P,P₅,P,house)-free
(C₅,P,P₅,house)-free
(C₅,P₂ ∪ P₃,house)-free
(C₅,P₅,A,C₆,P₆,co-domino)-free
(C₅,P₅,P,house)-free
(C₅,P₅,P₂ ∪ P₃)-free
(C₅,P₅,co-fish,fish,house)-free
(C₅,P₅,house)-free
(C₅,P₅)-free
(C₅,P₆,P₆)-free
(C₅,S₃,X₁₁,3K₂,C₇,P₂ ∪ P₄,X₁₇₃)-free
(C₅,S₃,3K₂,P₂ ∪ P₄)-free
(C₅,house)-free
C₅-free
(C₆,K_3,3+e,P,P₇,X₃₇,X₄₁)-free
(C₆,P₆,P₆,X₁₀,X₁₁,X₁₂,X₁₃,X₁₄,X₁₅,X₅,X₆,X₇,X₈,X₉,anti-hole,co-antenna)-free
(C₆,C₆)-free
(C₆,C₆)-free murky
(C₆,house)-free
(C₆,triangle)-free
C₆-free
C₆-free ∩ modular
CONV
(C_n+4,X₅₉,longhorn)-free
C_n+4-free
(C_n+6,odd-cycle)-free
C_n+6-free
C_n+7-free
(E,P)-free
E-free
EPT
Gallai
Gallai-perfect
(H,triangle)-free
HH-free
HHD-free
HHD-free ∩ co-HHD-free
HHDA-free
HHDbicycle-free
HHG-free
HHP-free
Hilbertian
(K_1,4,diamond)-free
(K_1,4,odd-cycle)-free
(K_1,4,paw)-free
K_1,4-free
(K_1,5,triangle)-free
(K₂ ∪ K₃,X₁₁,X₁₂₇,X₁₂₈,X₁₂₉,X₁₃₁,X₁₃₃,X₁₃₅,X₁₃₆,X₁₃₇,X₁₃₈,X₁₃₉,X₁₄₀,X₁₄₁,X₁₄₂,X₁₄₃,X₁₄₄,X₁₄₅,X₁₄₆,X₁₄₇,X₁₄₈,X₁₄₉,X₁₅₀,X₁₅₁,X₃₀,X₃₅,X₄₆,XF₁²ⁿ⁺³,XF₆²ⁿ⁺³,2P₃,3K₂,C₄ ∪ P₂,C₆,P₆,X₁₃₀,X₁₃₂,X₁₃₄,X₁₅₂,X₁₅₃,X₁₅₄,X₁₅₅,X₁₅₆,X₁₅₇,X₁₅₈,X₁₈,X₈₄,antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free
(K₂ ∪ K₃,P,anti-hole)-free
(K₂ ∪ K₃,P,house)-free
(K₂ ∪ K₃,house)-free
K₂ ∪ K₃-free
K₂ ∪ claw-free
(K_2,3,P,P₅)-free
(K_2,3,P,hole)-free
(K_2,3,P₅)-free
(K_2,3,diamond)-free
(K_2,3,diamond)-free ∩ weakly modular
K_2,3-free
(K₃ ∪ P₃,C₆,P,P₇,X₃₇,X₄₁)-free
(K_3,3,3,C_n+4)-free
(K_3,3,K_3,3+e,2P₃,C_n+4)-free
(K_3,3,K₅)-minor-free
(K_3,3,P₅)-free
(K_3,3,C_n+4)-free
(K_3,3-e,P₅,X₉₈)-free
(K_3,3-e,P₅,X₉₉)-free
(K_3,3-e,P₅)-free
(K_4,4,P₅)-free
(K₄,S₃,X₃₆,C₇,X₁₇₅,X₁₇₆,X₄₂,antenna,co-claw,net,odd-hole)-free
(K₄,S₃)-free
(K₄,odd anti-hole,odd-hole)-free
K₄-free
K₄-free ∩ perfect
(K₅ - e,W₅,A,C₄ ∪ 2K₁,P₂ ∪ P₃,R,claw,co-twin-C₅,co-twin-house)-free
Matula perfect
Meyniel
Meyniel ∩ co-Meyniel
Meyniel ∩ weakly chordal
(P,P₅)-free
(P,P₇)-free
(P,P₈)-free
(P,T₂)-free
(P,star_1,2,3)-free
(P,star_1,2,4)-free
(P,star_1,2,5)-free
P-free
(P₂ ∪ P₃,house)-free
P₂ ∪ P₄-free
P₄-bipartite
P₄-brittle
P₄-comparability
P₄-laden
P₄-simplicial
(P₅,X₈₂,X₈₃)-free
(P₅,A,anti-hole,co-domino)-free
(P₅,C₆)-free
(P₅,C₆)-free ∩ weakly chordal
(P₅,P,anti-hole)-free
(P₅,P₂ ∪ P₃)-free
(P₅,anti-hole,co-bicycle,co-domino)-free
(P₅,anti-hole,co-domino)-free
(P₅,anti-hole)-free
(P₅,house)-free
P₅-free
P₅-free ∩ weakly chordal
(P₆,X₁₀,X₁₁,X₁₂,X₁₃,X₁₄,X₁₅,X₅,X₆,X₇,X₈,X₉,C₆,P₆,antenna,hole)-free
(P₆,X₃₀,X₈)-free
P₆-free
P₇-free
(S₃,S₄,net)-free
(S₃,3K₂,E,P₂ ∪ P₄,odd anti-hole,odd-hole)-free
(S₃,3K₂,E,P₂ ∪ P₄)-free
(S₃,3K₂,E,odd-hole)-free
(S₃,C_n+6,X₃₇,antenna,co-claw,co-sun)-free
(S₃,co-claw,net)-free
(S₃,co-claw)-free
(S₃,net)-free
(S₃,net)-free ∩ sun-free
S₃-free
SEG
V-perfect
(W₄,W₅,butterfly)-free
(W₄,gem)-free
(W₄,gem)-free ∩ short-chorded
Welsh-Powell opposition
Welsh-Powell perfect
X-chordal
X-chordal ∩ X-conformal ∩ bipartite
X-chordal ∩ bipartite
X-conformal
X-conformal ∩ bipartite
X-conformal ∩ bipartite ∩ hereditary X-chordal
X-star-chordal
(X₁₂,X₅,X₉₅,X₉₆,X₉₇,X₁₂,X₅,X₉₅,X₉₆,X₉₇,claw ∪ triangle,claw ∪ triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free
(X₃₀,XZ₁,XZ₄,longhorn)-free
(X₃₈,gem,house)-free
(X₇₉,X₈₀)-free
(X₇₉,X₈₀)-free ∩ modular
XC₁₀-free
XC₁₀-free ∩ pseudo-modular
(XF₁²ⁿ⁺³,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,odd-hole)-free
(XF₁²ⁿ⁺³,XF₅²ⁿ⁺³,XF₆²ⁿ⁺²,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,anti-hole,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ,hole)-free
β-perfect
β-perfect ∩ co-β-perfect
β-perfect ∩ perfect
(G)-perfect
₃-perfect
2P₃-free
(3K₂,odd-hole,paw)-free
(A,P₆,co-domino)-free
BW₃-free
C₆-free
(C_n+4,X₅₉,co-longhorn)-free
C_n+4-free
(C_n+6,T₂,X₂,X₃,X₃₀,X₃₁,X₃₂,X₃₃,X₃₄,X₃₅,X₃₆,X₃₇,X₃₈,X₃₉,X₄₀,X₄₁,co-XF₂ⁿ⁺¹,co-XF₃ⁿ,co-XF₄ⁿ)-free
C_n+6-free
C_n+7-free
(E,P)-free
E-free
(K_1,4,P,co-fork,house)-free
(K_1,4,house)-free
K_1,4-free
K₂ ∪ claw-free
(P,P₇)-free
(P,P₈)-free
(P,T₂)-free
(P,star_1,2,3)-free
(P,co-star_1,2,4)-free
(P,co-star_1,2,5)-free
(P,house)-free
P-free
P₂ ∪ P₄-free
(P₆,X₃₀,X₈)-free
P₆-free
P₇-free
(W₄,W₅,co-butterfly)-free
(X₃₀,XZ₁,XZ₄,co-longhorn)-free
(X₇₉,X₈₀)-free
(X₈₂,X₈₃,house)-free
(n+4)-pan-free
absolute bipartite retract
absolutely perfect
absorbantly perfect
all-4-simplicial
alternately colourable
alternately orientable
(anti-hole,bull,odd-hole)-free
(anti-hole,co-sun,hole)-free
(anti-hole,hole,sun)-free
(anti-hole,hole)-free
(anti-hole,odd-hole)-free
anti-hole-free
b-perfect
b-perfect ∩ chordal
balanced
balanced 2-interval
balanced ∩ paw-free
biclique separable
bip^*
bipartite
bipartite ∩ co-perfectly orderable
bipartite ∩ maximum degree 3
bipartite ∩ weakly chordal
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
biplanar
bisplit
bisplit ∩ triangle-free
bridged
brittle
building-free
building-free ∩ even-signable
building-free ∩ odd-signable
(bull,co-fork)-free
(bull,hole,odd anti-hole)-free
(bull,house,odd-hole)-free
(bull,house)-free
(bull,odd anti-hole,odd-hole)-free
bull-free
bull-free ∩ perfect
(butterfly,gem)-free
caterpillar arboricity <= 2
charming
chordal
chordal ∩ co-chordal
chordal ∩ irredundance perfect
chordal ∪ co-chordal
chordal bipartite
circle
circle-polygon
circular perfect
claw-free
clique
clique separable
clique-Helly
clique-perfect
clique-perfect ∩ triangle-free
co-Gallai
co-HHD-free
co-Matula perfect
co-Meyniel
co-P₄-brittle
co-Welsh-Powell opposition
co-Welsh-Powell perfect
co-β-perfect
co-biclique separable
co-building-free
co-chordal
co-circular perfect
(co-claw,house)-free
(co-claw,odd anti-hole,odd-hole)-free
(co-claw,odd anti-hole)-free
(co-claw,odd-hole)-free
co-claw-free
co-comparability ∪ comparability
(co-cricket,house)-free
co-domino-free
(co-fork,hole)-free
(co-fork,house)-free
co-fork-free
co-interval filament
co-interval mixed
(co-odd building,odd anti-hole)-free
co-perfectly orderable
co-sun-free
co-trapezoid
cograph contraction
coin
comparability
comparability ∩ weakly chordal
comparability graphs of posets of interval dimension 2
comparability graphs of posets of interval dimension d
containment graphs
cop-win
(cross,triangle)-free
cycle-bicolorable
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
disk
disk contact
dismantlable
domination
domination perfect
domination perfect ∩ triangle-free
domino-free
even anti-cycle-free
even anti-hole-free
even-cycle-free
even-hole-free
even-hole-free ∩ probe chordal
even-signable
extended P₄-laden
fork-free
gem-free
generalized strongly chordal
genus 0
genus 1
good
graceful
grid
half-disk Helly
hereditary Matula perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary X-chordal
hereditary absolute bipartite retract
hereditary clique-Helly
hereditary clique-Helly ∩ paw-free ∩ perfect
hereditary dismantlable
hereditary maximal clique irreducible
hereditary modular
hereditary open-neighbourhood-Helly
hereditary perfect elimination bipartite
hereditary weakly modular
(hole,odd anti-hole)-free
(hole,odd-cycle)-free
hole-free
house-free
house-free ∩ weakly chordal
i-triangulated
induced-hereditary pseudo-modular
interval filament
irredundance perfect
irredundance perfect with ir(G)<= 4
isometric-HH-free
isometric-hereditary pseudo-modular
k-DIR
k-starlike
kernel solvable
line
line graphs of Helly hypergraphs of rank 3
line graphs of linear hypergraphs of rank 3
linear arboricity <= 2
locally perfect
maxibrittle
maximal clique irreducible
maximum degree 3
maximum degree 4
median
modular
modular ∩ open-neighbourhood-Helly
murky
(n+4)-pan-free
nK₂-free, fixed n
nP₃-free, fixed n
nearly bipartite
net-free
normal
(odd anti-hole,odd-hole)-free
odd anti-hole-free
(odd building,odd-hole)-free
odd co-sun-free
odd-cycle-free
(odd-hole,paw)-free
odd-hole-free
odd-hole-free ∩ planar
odd-hole-free ∩ pretty
odd-signable
odd-sun-free
open-neighbourhood-Helly
opposition
outer-string
overlap
(p,q<=2)-colorable
parity
partial 3d grid
partial bar visibility
partial grid
partial rectangle visibility
paw-free
paw-free ∩ perfect
perfect
perfect ∩ planar
perfect ∩ split-neighbourhood
perfect ∩ triangle-free
perfect connected-dominant
perfect elimination bipartite
perfectly 1-transversable
perfectly colorable
perfectly contractile
perfectly orderable
planar
planar ∩ triangle-free
planar of maximum degree 3
planar of maximum degree 4
polar
preperfect
pretty
probe Gallai
probe Meyniel
probe chordal
probe chordal ∩ weakly chordal
probe chordal bipartite
probe comparability
probe split
pseudo-median
pseudo-modular
pseudo-modular ∩ triangle-free
pseudo-split
quasi-Meyniel
quasi-brittle
quasi-line
quasi-median
quasi-parity
quasitriangulated
rectangle visibility
semiperfectly orderable
short-chorded
skeletal
slender
slightly triangulated
slim
spider graph
split
split-neighbourhood
split-perfect
strict quasi-parity
string
strong domination perfect
strongly 3-colorable
strongly circular perfect
strongly even-signable
strongly orderable
strongly perfect
subtree filament
subtree overlap
sun-free
sun-free ∩ weakly chordal
superbrittle
superperfect
thickness <= 2
toroidal
totally unimodular
triangle contact
triangle-free
triangulated
tripartite
undirected path
unimodular
unit 2-interval
unit disk
upper domination perfect
upper irredundance perfect
very strongly perfect
visibility
weak bar visibility
weak bipolarizable
weak bisplit
weak rectangle visibility
weakly chordal
weakly modular

Input:	A graph G in this class and an integer k.
Output:	True iff G contains a set S of vertices, with \|S\| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.

Problem: Domination

Linear

Polynomial

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI