Information System on Graph Classes and their Inclusions
Find class
Global
ISGCI home
Java
All classes
References
Smallgraphs
✉
This problem
Linear
Polynomial
NP-hard
NP-complete
coNP-complete
Open
Unknown
Problem: Clique
Definition:
Input:
A graph
G
in this class and an integer
k
.
Output:
True iff
G
contains a set
S
of pairwise adjacent vertices, with |
S
| >=
k
.
Linear
(0,2)-colorable
(0,2)-colorable ∩ chordal
(1,1)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar ∩ chordal
1-bounded bipartite
(2,0)-colorable ∩ chordal
2-bounded bipartite
2-leaf power
2-outerplanar
2-terminal series-parallel
2-tree
2-tree ∩ probe interval
(2C
4
,3K
2
,C
6
,E,P
2
∪ P
4
,P
6
,X
25
,X
26
,X
27
,X
28
,X
29
,odd-cycle)-free
(2K
2
,C
4
,C
5
,H,S
3
,X
160
,
X
159
,net,rising sun)-free
(2K
2
,C
4
,C
5
,S
3
,X
159
,X
160
,
H
,co-rising sun,net)-free
(2K
2
,C
4
,C
5
,S
3
,co-rising sun,net,rising sun)-free
(2K
2
,C
4
,C
5
,S
3
,co-rising sun,net)-free
(2K
2
,C
4
,C
5
,S
3
,net,rising sun)-free
(2K
2
,C
4
,C
5
,S
3
,net)-free
(2K
2
,C
4
,C
5
,co-sun)-free
(2K
2
,C
4
,C
5
,sun)-free
(2K
2
,C
4
,C
5
)-free
(2K
2
,C
4
,P
4
)-free
(2K
2
,C
5
,S
3
,X
159
,X
160
,X
161
,X
162
,X
46
,X
70
,
2P
3
,
3K
2
,
H
,
P
2
∪ P
4
,
X
1
,co-rising sun,house,net)-free
(2K
2
,C
5
,triangle)-free
(2K
2
,K
3,3
,K
3,3
+e,P
4
,
2P
3
)-free
(2K
2
,P
4
,co-dart)-free
(2K
2
,P
4
)-free
2K
2
-free ∩ bipartite
2K
2
-free ∩ probe trivially perfect
(2K
3
+ e,A,C
5
,C
6
,E,H,K
3,3
-e,P
6
,R,S
3
,X
166
,X
167
,X
168
,X
169
,X
170
,X
171
,X
172
,X
18
,X
45
,X
5
,X
58
,X
84
,X
95
,X
96
,X
98
,
A
,
C
6
,
E
,
H
,
P
6
,
R
,
X
166
,
X
167
,
X
168
,
X
169
,
X
170
,
X
171
,
X
172
,
X
18
,
X
45
,
X
5
,
X
58
,
X
84
,
X
95
,
X
96
,
X
98
,antenna,co-antenna,co-cross,co-domino,co-fish,co-twin-house,cross,domino,fish,net,twin-house)-free
(2K
3
+ e,A,C
5
,C
6
,E,K
3,3
-e,P
6
,R,X
166
,X
167
,X
169
,X
170
,X
171
,X
172
,X
18
,X
45
,X
5
,X
58
,X
84
,X
95
,X
98
,
A
,
C
6
,
E
,
P
6
,
R
,
X
166
,
X
167
,
X
169
,
X
170
,
X
171
,
X
172
,
X
18
,
X
45
,
X
5
,
X
58
,
X
84
,
X
95
,
X
98
,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free
(2K
3
,2P
3
,C
4
,K
3
∪ P
3
,P
4
)-free
(2K
3
,2P
3
,C
n+4
,K
3
∪ P
3
)-free
(2K
3
,C
n+4
)-free
(2P
3
,3K
2
,C
4
,C
5
,H,P
2
∪ P
4
,P
5
,S
3
,X
1
,X
160
,
X
159
,
X
161
,
X
162
,
X
46
,
X
70
,net,rising sun)-free
3-leaf power
3-tree
3-tree ∩ planar
(3K
1
,C
4
,C
5
)-free
(3K
1
,C
5
,butterfly,diamond)-free
(3K
1
,P
4
)-free
(3K
1
,
T
2
,
X
2
,
X
3
,anti-hole)-free
(3K
1
,co-fork)-free
(3K
1
,house)-free
(3K
1
,paw)-free
(3K
2
,C
4
∪ P
2
,C
5
,P
2
∪ P
4
,P
5
,S
3
,X
1
,X
46
,X
70
,
3K
2
,
C
4
∪ P
2
,
P
2
∪ P
4
,
X
1
,
X
46
,
X
70
,co-fish,co-rising sun,fish,house,net,rising sun)-free
(3K
2
,C
5
,P
2
∪ P
4
,XZ
11
,XZ
12
,XZ
13
,XZ
14
,XZ
6
,XZ
7
,XZ
8
,XZ
9
,
XZ
11
,
XZ
12
,
XZ
13
,
XZ
14
,
XZ
6
,
XZ
7
,
XZ
8
,
XZ
9
,net)-free
(3K
2
,C
6
,P
7
,X
164
,X
165
,odd-cycle,sunlet
4
)-free
(3P
3
,C
n+4
,P
3
∪ P
4
,P
5
,X
102
,X
180
,X
181
,X
182
,X
183
,
A
)-free
(4K
1
,K
4
)-free
(4K
1
,P
4
)-free
(5,1)
(5,2)-crossing-chordal
5-leaf power ∩ distance-hereditary
(6,1)-chordal ∩ bipartite
(6,2)
(6,2)-chordal ∩ bipartite
(7,3)
(7,4)
(8,4)
(9,6)
(A,C
5
,P
5
,
A
,house,parachute,parapluie)-free
(A,T
2
,odd-cycle)-free
(A,
3P
3
,
C
n+4
,
P
3
∪ P
4
,
X
102
,
X
180
,
X
181
,
X
182
,
X
183
,house)-free
AC
AT-free ∩ bipartite
Apollonian network
BW
3
-free ∩ modular
(C
4
,C
6
,odd-cycle)-free
(C
4
,P
4
,dart)-free
(C
4
,P
4
)-free
C
4
-free ∩ C
6
-free ∩ bipartite
(C
5
,C
6
∪ K
1
,C
7
,K
3,3
∪ K
1
,K
3,3
-e ∪ K
1
,
K
5
- e
,domino ∪ K
1
,triangle)-free
(C
5
,C
6
,P
6
,X
17
,X
18
,X
5
,X
98
,
C
6
,
P
6
,antenna,domino)-free
(C
5
,K
2
∪ K
3
,K
2,3
,P,P
2
∪ P
3
,P
5
,
P
,
P
2
∪ P
3
,co-fork,fork,house)-free
(C
5
,P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
(C
5
,P,P
5
,
P
,co-fork,fork,house)-free
(C
5
,P,P
5
,
P
,house)-free
(C
5
,P,P
5
,house)-free
(C
5
,P
5
,
P
,house)-free
(C
5
,P
5
,co-fish,fish,house)-free
(C
5
,P
5
,house)-free
(C
5
,S
3
,XZ
11
,XZ
12
,XZ
13
,XZ
14
,XZ
6
,XZ
7
,XZ
8
,XZ
9
,
3K
2
,
P
2
∪ P
4
,
XZ
11
,
XZ
12
,
XZ
13
,
XZ
14
,
XZ
6
,
XZ
7
,
XZ
8
,
XZ
9
)-free
(C
5
,S
3
,
3K
2
,
P
2
∪ P
4
)-free ∩ P
4
-tidy
(C
5
,XZ
11
,XZ
12
,XZ
13
,XZ
14
,XZ
6
,XZ
7
,XZ
8
,XZ
9
,
XZ
11
,
XZ
12
,
XZ
13
,
XZ
14
,
XZ
6
,
XZ
7
,
XZ
8
,
XZ
9
)-free
(C
5
,co-butterfly,co-diamond,triangle)-free
C
5
-free ∩ P
4
-extendible
C
5
-free ∩ P
4
-tidy
C
5
-free ∩ matrogenic
C
6
-free ∩ modular
(C
n+4
∪ K
1
,C(n,k),W
4
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
∪ K
1
,C(n,k),X
42
,
T
2
,
X
2
,
X
3
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
∪ K
1
,S
3
∪ K
1
,X
42
,
T
2
,
X
2
,
X
3
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
∪ K
1
,S
3
,W
4
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
,P
5
,bull)-free
(C
n+4
,P
5
,claw,gem)-free
(C
n+4
,S
3
∪ K
1
,claw,net)-free
(C
n+4
,S
3
,claw,net)-free
(C
n+4
,XF
1
2n+3
,XF
6
2n+2
,
X
34
,
X
36
,co-XF
2
n+1
,co-XF
3
n
)-free
(C
n+4
,bull,dart,gem)-free
(C
n+4
,claw,gem)-free
(C
n+4
,diamond)-free
(C
n+4
,gem)-free
(C
n+6
,T
2
,X
2
,X
3
,X
30
,X
31
,X
32
,X
33
,X
34
,X
36
,XF
1
2n+3
,XF
2
n+1
,XF
3
n
,XF
4
n
,XF
5
2n+3
,XF
6
2n+2
,
C
n+6
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
36
,co-XF
1
2n+3
,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
,co-XF
5
2n+3
,co-XF
6
2n+2
,odd anti-hole)-free
(C
n+6
,T
2
,X
2
,X
3
,X
30
,X
31
,X
32
,X
33
,X
34
,X
36
,XF
1
2n+3
,XF
2
n+1
,XF
3
n
,XF
4
n
,XF
5
2n+3
,XF
6
2n+2
,
C
n+6
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
36
,co-XF
1
2n+3
,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
,co-XF
5
2n+3
,co-XF
6
2n+2
,odd-hole)-free
(C
n+6
,odd-cycle)-free
Dilworth 1
Dilworth 2
(E,odd-cycle)-free
E-free ∩ bipartite
HHD-free ∩ co-HHD-free
HHDG-free
HHDbicycle-free
Halin
Hilbertian
(K
1,4
,odd-cycle)-free
(K
2
∪ K
3
,P
4
,butterfly)-free
(K
2
∪ K
3
,
P
,
X
163
,
X
95
,co-diamond,house)-free
(K
2,3
,K
4
)-minor-free
(K
2,3
,P,P
5
,X
163
,X
95
,diamond)-free
(K
2,3
,P
4
,co-butterfly)-free
K
2,3
-free ∩ hereditary modular
K
3
-minor-free
(K
4
,P
4
)-free
K
4
-minor-free
(K
5
,X
126
,X
174
,
3K
2
)-minor-free
Matula perfect
Meyniel ∩ co-Meyniel
(P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
(P,P
5
,
P
,co-fork,fork,house)-free
(P,
P
,co-fork,fork)-free
P
3
-free
(P
4
,triangle)-free
P
4
-extendible
P
4
-extendible ∩ P
4
-sparse
P
4
-free
P
4
-laden
P
4
-lite
P
4
-reducible
P
4
-sparse
P
4
-tidy
P
4
-tidy ∩ (S
3
,
3K
2
,
E
,
P
2
∪ P
4
,odd anti-hole,odd-hole)-free
P
4
-tidy ∩ balanced
P
4
-tidy ∩ hereditary clique-Helly ∩ perfect
P
4
-tidy ∩ perfect
(P
5
,S
3
,
A
,
E
,
X
1
,anti-hole,co-domino,co-rising sun,net)-free
(P
5
,bull,house)-free
(P
5
,bull)-free ∩ interval
(P
5
,co-fork,house)-free
(P
5
,diamond)-free
(P
5
,fork,house)-free
(P
5
,triangle)-free
(P
6
,X
10
,X
11
,X
12
,X
13
,X
14
,X
15
,X
5
,X
6
,X
7
,X
8
,X
9
,
C
6
,
P
6
,antenna,hole)-free
(P
7
,odd-cycle,star
1,2,3
,sunlet
4
)-free
(P
7
,odd-cycle,star
1,2,3
)-free
PURE-2-DIR
(S
3
,
C
n+4
,co-claw,net)-free
(S
3
,claw,net)-free ∩ chordal
(S
3
,net)-free ∩ extended P
4
-sparse
(S
3
,net)-free ∩ split
SC 2-tree
SC 3-tree
SC k-tree, fixed k
(T
2
,X
2
,X
3
,hole,triangle)-free
(T
2
,cycle)-free
(T
3
,X
81
,cycle)-free
(T
3
,cycle)-free
V-perfect
Welsh-Powell perfect
X-chordal ∩ X-conformal ∩ bipartite
X-chordal ∩ bipartite
X-conformal ∩ bipartite
X-conformal ∩ bipartite ∩ hereditary X-chordal
X-star-chordal
(X
177
,odd-cycle)-free
(X
79
,X
80
)-free ∩ modular
(XC
1
,XC
2
,XC
3
,XC
4
,XC
5
,XC
6
,XC
7
,XC
8
)-free
(XC
12
,cycle)-free
XC
9
-free
(XF
1
2n+3
,XF
5
2n+3
,XF
6
2n+2
,
C
n+6
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
35
,
X
36
,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
,odd-hole)-free
(XF
1
2n+3
,XF
5
2n+3
,XF
6
2n+2
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
35
,
X
36
,anti-hole,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
,hole)-free
(XZ
11
,XZ
12
,XZ
13
,XZ
14
,XZ
6
,XZ
7
,XZ
8
,XZ
9
,
XZ
11
,
XZ
12
,
XZ
13
,
XZ
14
,
XZ
6
,
XZ
7
,
XZ
8
,
XZ
9
)-free
(
2C
4
,
3K
2
,
C
6
,
E
,
P
2
∪ P
4
,
P
6
,
X
25
,
X
26
,
X
27
,
X
28
,
X
29
,odd anti-cycle)-free
(
3K
2
,odd-hole,paw)-free
(
C
n+4
,
T
2
,
X
31
,co-XF
2
n+1
,co-XF
3
n
)-free
(
C
n+4
,bull,house)-free
(
C
n+4
,co-claw,co-gem,house)-free
(
P
,butterfly,fork,gem)-free
(
P
,fork,gem)-free
(
P
,fork,house)-free
P
3
-free
(
T
2
,co-cycle)-free
absolute bipartite retract
almost CIS
almost tree (1)
astral triple-free
b-perfect ∩ chordal
balanced ∩ paw-free
bi-cograph
biconvex
binary tree
binary tree ∩ partial grid
bipartite
bipartite ∩ bithreshold
bipartite ∩ bounded tolerance
bipartite ∩ boxicity 2
bipartite ∩ bridged
bipartite ∩ claw-free
bipartite ∩ co-comparability
bipartite ∩ co-perfectly orderable
bipartite ∩ co-trapezoid
bipartite ∩ convex-round
bipartite ∩ distance-hereditary
bipartite ∩ grid intersection
bipartite ∩ maximum degree 3
bipartite ∩ module-composed
bipartite ∩ probe interval
bipartite ∩ tolerance
bipartite ∩ trapezoid
bipartite ∩ weakly chordal
bipartite chain
bipartite permutation
bipartite tolerance
bisplit
bisplit ∩ triangle-free
block
bounded treewidth
(bull,co-fork,fork)-free
(bull,fork,gem)-free
(bull,fork,house)-free
(bull,house,odd-hole)-free
cactus
caterpillar
chordal ∩ co-chordal
chordal ∩ co-chordal ∩ co-comparability ∩ comparability
chordal ∩ cograph
chordal ∩ comparability
chordal ∩ diamond-free
chordal ∩ distance-hereditary
chordal ∩ domino
chordal ∩ gem-free
chordal ∩ maximal planar
chordal ∩ proper circular arc
chordal ∩ unit circular arc
chordal bipartite
circle graph with equator
circular arc ∩ cograph
circular arc ∩ comparability
circular convex bipartite
circular permutation
(claw ∪ 3K
1
,odd-cycle)-free
(claw,co-claw)-free
(claw,odd-cycle)-free
(claw,paw)-free
claw-free ∩ interval
cliquewidth 2
co-bipartite ∩ proper circular arc
co-bithreshold ∩ split
co-bounded tolerance
co-chordal ∩ comparability
co-chordal ∩ superperfect
(co-claw,co-paw)-free
(co-claw,odd anti-cycle)-free
co-comparability ∩ comparability
(co-diamond,diamond)-free
(co-fork,odd anti-cycle)-free
co-interval
co-interval ∩ cograph
co-interval ∩ cograph ∩ interval
co-interval ∩ interval
(co-paw,paw)-free
(co-paw,triangle)-free
co-probe threshold
co-proper interval bigraph
co-trapezoid
co-trivially perfect
co-trivially perfect ∩ trivially perfect
cograph
cograph ∩ interval
cograph ∩ split
comparability
comparability ∩ split
comparability ∩ weakly chordal
comparability graphs of arborescence orders
comparability graphs of dimension 2 posets
comparability graphs of dimension 3 posets
comparability graphs of dimension 4 posets
comparability graphs of dimension d posets
comparability graphs of posets of interval dimension 2
comparability graphs of posets of interval dimension 2, height 1
comparability graphs of posets of interval dimension d
comparability graphs of semiorders
comparability graphs of series-parallel posets
comparability graphs of threshold orders
containment graph of circles
containment graph of intervals
containment graphs
containment graphs of circular arcs
convex
cycle-free
difference
distance-hereditary
(domino,gem,house)-free ∩ pseudo-modular
(domino,hole,odd-cycle)-free
domino-free ∩ modular
domishold
extended P
4
-reducible
extended P
4
-sparse
(fork,odd-cycle)-free
(fork,triangle)-free
grid
half-disk Helly
hereditary Matula perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary absolute bipartite retract
hereditary clique-Helly ∩ paw-free ∩ perfect
hereditary median
hereditary modular
hereditary perfect elimination bipartite
(hole,odd-cycle)-free
homogeneously representable
independent module-composed
indifference
intersection graph of nested intervals
interval bigraph
interval containment bigraph
k-path graph, fixed k
k-tree, fixed k
line graphs of acyclic multigraphs
matrogenic
matroidal
maxibrittle
maximal outerplanar
median
minimally imperfect
modular
modular ∩ open-neighbourhood-Helly
(odd-cycle,star
1,2,3
,sunlet
4
)-free
(odd-cycle,star
1,2,3
)-free
odd-cycle-free
(odd-hole,paw)-free
outerplanar
partial 2-tree
partial 3-tree
partial 3-tree ∩ planar
partial 4-tree
partial grid
partial k-tree, fixed k
partner-limited
paw-free ∩ perfect
perfect ∩ triangle-free
perfect elimination bipartite
perfectly colorable
permutation
permutation ∩ split
probe bipartite chain
probe co-trivially perfect ∩ probe trivially perfect
probe interval ∩ tree
probe interval bigraph
probe threshold
probe threshold ∩ split
proper Helly circular arc
proper circular arc
proper interval
proper interval bigraph
pseudo-modular ∩ triangle-free
ptolemaic
ptolemaic ∩ weakly geodetic
(q, q-3), fixed q>= 7
(q,q-4), fixed q
quasi-threshold
semi-P
4
-sparse
semicircular
series-parallel
split
split ∩ strongly chordal
split ∩ superperfect
split ∩ threshold signed
strict 2-threshold
superbrittle
superfragile
thick tree
threshold
threshold signed
tolerance ∩ tree
tolerance ∩ triangle-free
tree
treewidth 2
treewidth 3
treewidth 4
treewidth 5
trivially perfect
unit Helly circular arc
unit circular arc
unit interval
unit interval bigraph
back to top
Polynomial
(0,3)-colorable
(0,3)-colorable ∩ chordal
(1,2)-polar
1-DIR
1-bounded tripartite
(2,0)-colorable
(2,2)-colorable ∩ chordal
2-DIR
2-connected ∩ (4-fan,C
n+4
,K
5
- e,S
3
,
H
,
K
3
∪ 2K
1
)-free
2-split ∩ perfect
2-subdivision
2-subdivision ∩ planar
2-thin
2-threshold
(2K
2
,4K
1
,co-claw,co-diamond)-free
(2K
2
,C
4
)-free
(2K
2
,C
5
,
C
6
,
C
7
,
C
8
,co-claw,co-diamond)-free
(2K
2
,C
5
,
T
2
)-free
(2K
2
,
C
6
,odd anti-cycle)-free
(2K
2
,
P
6
)-free
(2K
2
,
X
91
,co-claw)-free
(2K
2
,house)-free
(2K
2
,odd anti-hole)-free
2K
2
-free ∩ probe cograph
(2K
3
+ e,A,C
6
,E,K
3,3
-e,P
6
,R,X
166
,X
167
,X
169
,X
170
,X
171
,X
172
,X
18
,X
45
,X
5
,X
58
,X
84
,X
95
,X
98
,
A
,
C
6
,
E
,
P
6
,
R
,
X
166
,
X
167
,
X
169
,
X
170
,
X
171
,
X
172
,
X
18
,
X
45
,
X
5
,
X
58
,
X
84
,
X
95
,
X
98
,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free
(2K
3
+ e,C
5
,C
6
,P
6
,X
5
,
2P
4
,
A
,
C
6
,
C
7
,
E
,
P
7
,
R
,
X
1
,
X
103
,
X
5
,
X
58
,
X
84
,
X
98
,antenna,co-domino,co-rising sun,co-twin-house,domino,parachute,parapluie,rising sun,sunlet
4
)-free
(2K
3
+ e,
X
98
,house)-free
(2K
3
+ e,
X
99
,house)-free
(2K
3
+ e,house)-free
(2K
3
,2P
3
,C
5
,C
6
,C
7
,K
2,3
,K
3
∪ P
3
,X
84
,
3K
2
,
C
4
∪ P
2
,
C
6
,
P
2
∪ P
4
,
P
6
,
X
18
,
X
5
,co-antenna,co-domino,co-fish)-free
(2K
3
,4K
1
,C
7
,X
38
,X
39
,
W
4
∪ K
1
,
W
5
,
X
86
,
X
87
,
X
88
,
X
89
,
X
90
,butterfly ∪ K
1
,diamond)-free
(2K
3
,house)-free
(2K
4
,house)-free
(2P
3
,3K
2
,C
4
∪ P
2
,C
6
,K
2,3
,P
6
,X
130
,X
132
,X
134
,X
152
,X
153
,X
154
,X
155
,X
156
,X
157
,X
158
,X
18
,X
84
,
X
11
,
X
127
,
X
128
,
X
129
,
X
131
,
X
133
,
X
135
,
X
136
,
X
137
,
X
138
,
X
139
,
X
140
,
X
141
,
X
142
,
X
143
,
X
144
,
X
145
,
X
146
,
X
147
,
X
148
,
X
149
,
X
150
,
X
151
,
X
30
,
X
35
,
X
46
,co-XF
1
2n+3
,co-XF
6
2n+3
,co-antenna,co-eiffeltower,co-longhorn,domino,fish,odd anti-hole)-free
(2P
3
,triangle)-free
(2P
4
,A,C
5
,C
6
,C
7
,E,K
3,3
-e,P
7
,R,X
1
,X
103
,X
5
,X
58
,X
84
,X
98
,
C
6
,
P
6
,
X
5
,
sunlet
4
,co-antenna,co-domino,co-rising sun,domino,parachute,parapluie,rising sun,twin-house)-free
(3K
1
,C
5
,K
5
- e,
C
6
∪ K
1
,
C
7
,
K
3,3
∪ K
1
,
K
3,3
-e ∪ K
1
,
domino ∪ K
1
)-free
(3K
1
,
E
)-free
(3K
1
,
K
2
∪ claw
)-free
(3K
1
,
P
6
)-free
(3K
1
,
X
172
)-free
(3K
2
,A,C
4
∪ 2K
1
,E,P
2
∪ P
3
,R,
K
5
- e
,co-claw,net,odd anti-hole,twin-house)-free
(3K
2
,C
4
∪ P
2
,C
5
,C
6
,K
2
∪ K
3
,K
3,3
,K
3,3
+e,P
2
∪ P
4
,P
6
,X
18
,X
5
,
2P
3
,
C
6
,
C
7
,
X
84
,antenna,domino,fish)-free
(3K
2
,E,P
2
∪ P
4
,net,odd anti-hole,odd-hole)-free
(3K
2
,
P
,co-gem,house)-free
(3K
2
,co-paw,odd anti-hole)-free
(3K
2
,triangle)-free
(3K
3
,C
n+4
)-free
(3P
3
,P
3
∪ P
4
,P
5
,X
102
,X
180
,X
181
,X
182
,X
183
,X
184
,X
185
,X
186
,X
187
,X
188
,X
189
,X
190
,X
191
,X
192
,X
193
,
5-pan
,
A
,
P
6
,co-twin-C
5
)-free
(4-fan,C
n+4
,K
5
- e,S
3
,X
100
,X
101
,X
102
,
H
,
K
3
∪ 2K
1
)-free
(4-fan,C
n+4
,K
5
- e,S
3
,
H
,
K
3
∪ 2K
1
)-free
4-leaf power
(4K
1
,C
7
,S
3
,X
175
,X
176
,X
42
,
X
36
,claw,co-antenna,net,odd anti-hole)-free
(4K
1
,C
7
,X
195
,X
196
,X
38
,X
39
,
W
5
,
X
194
,
X
86
,
X
88
,
X
89
,
X
90
,house)-free
(4K
1
,
C
n+4
)-free
(4K
1
,co-claw,co-diamond)-free
(4K
1
,odd anti-hole,odd-hole)-free
(5,2)-chordal
(5,2)-odd-chordal
(5,2)-odd-crossing-chordal
(5,2)-odd-noncrossing-chordal
5-leaf power
(5-pan,A,P
6
,X
186
,
3P
3
,
P
3
∪ P
4
,
X
102
,
X
180
,
X
181
,
X
182
,
X
183
,
X
184
,
X
185
,
X
187
,
X
188
,
X
189
,
X
190
,
X
191
,
X
192
,
X
193
,house,twin-C
5
)-free
(A,C
4
∪ 2K
1
,P
2
∪ P
3
,R,
K
5
- e
,
W
5
,co-claw,twin-C
5
,twin-house)-free
(A,C
4
∪ 2K
1
,P
2
∪ P
3
,R,
K
5
- e
,co-claw,odd anti-hole,twin-house)-free
(A,C
5
,C
6
,P
6
,domino,house)-free
(A,E,S
3
,X
1
,domino,hole,house,net,rising sun)-free
(A,H,K
3,3
,K
3,3
-e,T
2
,X
18
,X
45
,domino,triangle)-free
(A,H,K
3,3
,X
45
,triangle)-free
(A,P
6
,clique wheel,domino,hole,house)-free
AT-free ∩ chordal
(BW
3
,C
5
,K
3,4
,K
3,4
-e,T
2
,X
18
,X
92
,X
93
,triangle)-free
Berge
Berge ∩ bull-free
Berge ∩ claw-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,K
1,4
,X
85
,triangle)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,X
85
,triangle)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,X
85
,triangle)-free ∩ K
1,4
-free
(C
4
,C
5
,C
6
,C
7
,C
8
,claw,diamond)-free
(C
4
,C
5
,C
6
,S
3
)-free
(C
4
,C
5
,K
4
,diamond)-free
(C
4
,C
5
,K
4
,diamond)-free ∩ planar
(C
4
,C
5
,T
2
)-free
(C
4
,C
5
)-free
(C
4
,C
5
)-free ∩ Helly
(C
4
,C
5
)-free ∩ cop-win
(C
4
,K
4
,claw,diamond)-free
(C
4
,P
5
)-free
(C
4
,P
6
)-free
(C
4
,S
3
)-free
(C
4
,X
91
,claw)-free
(C
4
,
A
,
H
)-free
(C
4
,co-claw)-free
(C
4
,diamond)-free
(C
4
,odd-hole)-free
(C
4
,triangle)-free
(C
4
,triangle)-free ∩ planar
C
4
-free
C
4
-free ∩ co-comparability
C
4
-free ∩ induced-hereditary pseudo-modular
(C
5
,C
6
,C
7
,C
8
,P
8
,X
19
,X
20
,X
21
,X
22
,gem,house)-free
(C
5
,C
6
,P
6
,
C
6
,
P
6
,
X
17
,
X
18
,
X
5
,
X
98
,co-antenna,co-domino)-free
(C
5
,C
6
,P
6
,
C
6
,
P
6
)-free
(C
5
,C
6
,X
164
,X
165
,sunlet
4
,triangle)-free
(C
5
,K
3,3
-e,T
2
,X
18
,X
94
,domino,triangle)-free
(C
5
,P,
P
,bull,co-fork,gem,house)-free
(C
5
,P,co-fork,fork,gem,house)-free
(C
5
,P
2
∪ P
3
,house)-free
(C
5
,P
5
,
A
,
C
6
,
P
6
,co-domino)-free
(C
5
,P
5
,
C
6
,
C
7
,
C
8
,
P
8
,
X
19
,
X
20
,
X
21
,
X
22
,co-gem)-free
(C
5
,P
5
,
P
,co-fork,co-gem,fork)-free
(C
5
,P
5
,
P
2
∪ P
3
)-free
(C
5
,P
5
,gem)-free
(C
5
,P
6
,
P
6
)-free
(C
5
,S
3
,X
11
,
3K
2
,
C
7
,
P
2
∪ P
4
,
X
173
)-free ∩ co-line
(C
5
,bull,co-gem,gem)-free
(C
5
,co-gem,gem)-free
(C
5
,co-gem,house)-free
(C
6
,K
2
∪ K
3
,X
103
,X
37
,X
88
,X
90
,
C
n+4
∪ K
1
,
T
2
,
net ∪ K
1
,co-diamond,co-domino,co-eiffeltower,co-twin-C
5
)-free
(C
6
,P
6
,
P
6
,
X
10
,
X
11
,
X
12
,
X
13
,
X
14
,
X
15
,
X
5
,
X
6
,
X
7
,
X
8
,
X
9
,anti-hole,co-antenna)-free
(C
6
,
C
6
)-free murky
(C
6
,triangle)-free
(C
n+3
∪ K
1
,diamond,paw)-free
(C
n+4
∪ K
1
,K
2,3
,T
2
,
C
6
,
X
103
,
X
37
,
X
88
,
X
90
,diamond,domino,eiffeltower,net ∪ K
1
,twin-C
5
)-free
(C
n+4
∪ K
1
,K
2,3
,T
2
,
X
90
,domino,paw,twin-C
5
)-free
(C
n+4
,H)-free
(C
n+4
,K
4
)-free
(C
n+4
,S
3
∪ K
1
,
X
103
,claw,eiffeltower,net ∪ K
1
)-free
(C
n+4
,S
3
,net)-free
(C
n+4
,S
3
)-free
(C
n+4
,T
2
,X
31
,XF
2
n+1
,XF
3
n
)-free
(C
n+4
,T
2
,XF
2
n+1
)-free
(C
n+4
,T
2
,net)-free
(C
n+4
,X
59
,longhorn)-free
(C
n+4
,claw,net)-free
(C
n+4
,claw)-free
(C
n+4
,odd-sun)-free
(C
n+4
,sun)-free
C
n+4
-free
(C
n+6
,T
2
,X
2
,X
3
,X
30
,X
31
,X
32
,X
33
,X
34
,X
35
,X
36
,XF
2
n+1
,XF
3
n
,XF
4
n
,co-XF
1
2n+3
,co-XF
5
2n+3
,co-XF
6
2n+2
,odd anti-hole)-free
D
Dilworth 3
Dilworth 4
(E,triangle)-free
EPT ∩ chordal
F
n
grid
Gallai
Gallai-perfect
(H,K
3
∪ 2K
1
,
C
n+4
,
K
5
- e
,
X
100
,
X
101
,
X
102
,co-4-fan,net)-free
(H,K
3
∪ 2K
1
,
C
n+4
,
K
5
- e
,co-4-fan,net)-free
(H,triangle)-free
HH-free
HHD-free
HHDA-free
HHDS-free
HHG-free
HHP-free
Helly ∩ bridged
Helly chordal
Helly chordal ∩ clique-chordal
Helly circle
Helly circular arc
Helly circular arc ∩ self-clique
H
n,q
grid
(K
1,4
,diamond)-free
(K
1,4
,paw)-free
(K
1,5
,triangle)-free
(K
2
∪ K
3
,X
11
,X
127
,X
128
,X
129
,X
131
,X
133
,X
135
,X
136
,X
137
,X
138
,X
139
,X
140
,X
141
,X
142
,X
143
,X
144
,X
145
,X
146
,X
147
,X
148
,X
149
,X
150
,X
151
,X
30
,X
35
,X
46
,XF
1
2n+3
,XF
6
2n+3
,
2P
3
,
3K
2
,
C
4
∪ P
2
,
C
6
,
P
6
,
X
130
,
X
132
,
X
134
,
X
152
,
X
153
,
X
154
,
X
155
,
X
156
,
X
157
,
X
158
,
X
18
,
X
84
,antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free
(K
2
∪ K
3
,X
90
,
C
n+4
∪ K
1
,
T
2
,co-domino,co-paw,co-twin-C
5
)-free
(K
2
∪ K
3
,
P
,anti-hole)-free
(K
2
∪ K
3
,
P
,house)-free
(K
2
∪ K
3
,house)-free
(K
2
∪ claw,triangle)-free
(K
2,3
,X
37
,X
38
,diamond,domino,house,twin-C
5
)-free
(K
2,3
,diamond)-free
(K
2,3
,diamond)-free ∩ weakly modular
(K
3
∪ P
3
,
C
6
,
P
,
P
7
,
X
37
,
X
41
)-free
(K
3,3,3
,
C
n+4
)-free
(K
3,3
,K
3,3
+e,
2P
3
,
C
n+4
)-free
(K
3,3
,K
4
,W
4
∪ K
1
,W
5
,X
86
,X
87
,X
88
,X
89
,X
90
,
C
7
,
X
38
,
X
39
,
butterfly ∪ K
1
,co-diamond)-free
(K
3,3
,K
5
)-minor-free
(K
3,3
,
C
n+4
)-free
(K
4
,P
5
,W
5
,X
194
,X
86
,X
88
,X
89
,X
90
,
C
7
,
X
195
,
X
196
,
X
38
,
X
39
)-free
(K
4
,P
5
)-free
(K
4
,S
3
,X
36
,
C
7
,
X
175
,
X
176
,
X
42
,antenna,co-claw,net,odd-hole)-free
(K
4
,S
3
)-free
(K
4
,claw,diamond)-free
(K
4
,odd anti-hole,odd-hole)-free
K
4
-free
K
4
-free ∩ perfect
(K
5
- e,S
3
,
3K
2
,
A
,
C
4
∪ 2K
1
,
E
,
P
2
∪ P
3
,
R
,claw,co-twin-house,odd-hole)-free
(K
5
- e,W
5
,
A
,
C
4
∪ 2K
1
,
P
2
∪ P
3
,
R
,claw,co-twin-C
5
,co-twin-house)-free
(K
5
- e,
A
,
C
4
∪ 2K
1
,
P
2
∪ P
3
,
R
,claw,co-twin-house,odd-hole)-free
Meyniel
Meyniel ∩ weakly chordal
N
*
-perfect
(P,P
5
,
3K
2
,gem)-free
(P,P
5
,co-fork)-free
(P,co-butterfly,co-fork,co-gem)-free
(P,co-fork,co-gem)-free
(P,co-fork)-free
(P,co-gem,house)-free
(P
2
∪ P
3
,house)-free
(P
2
∪ P
4
,triangle)-free
P
4
-brittle
P
4
-comparability
P
4
-indifference
P
4
-simplicial
(P
5
,
A
,
P
6
,anti clique wheel,anti-hole,co-domino)-free
(P
5
,
A
,anti-hole,co-domino)-free
(P
5
,
C
6
)-free ∩ weakly chordal
(P
5
,
P
,anti-hole)-free
(P
5
,
P
,gem)-free
(P
5
,
P
2
∪ P
3
)-free
(P
5
,anti-hole,co-bicycle,co-domino)-free
(P
5
,anti-hole,co-domino,co-gem)-free
(P
5
,anti-hole,co-domino,co-sun)-free
(P
5
,anti-hole,co-domino)-free
(P
5
,anti-hole,co-gem)-free
(P
5
,anti-hole)-free
(P
5
,bull,co-fork)-free
(P
5
,bull,odd anti-hole)-free
(P
5
,co-fork)-free
(P
5
,gem)-free
(P
5
,house)-free
P
5
-free ∩ tripartite
P
5
-free ∩ weakly chordal
(P
6
,triangle)-free
P
6
-free ∩ tripartite
PI
PI
*
PURE-3-DIR
(S
3
,T
2
,X
2
,X
3
,
C
n+4
∪ K
1
,
C(n,k)
,
X
42
,even-hole,odd-cycle ∪ K
1
)-free
(S
3
,T
2
,X
2
,X
3
,
C
n+4
∪ K
1
,
S
3
∪ K
1
,
X
42
,even-hole,odd-cycle ∪ K
1
)-free
(S
3
,
3K
2
,
E
,
P
2
∪ P
4
,odd anti-hole,odd-hole)-free
(S
3
,
3K
2
,
E
,
P
2
∪ P
4
)-free
(S
3
,
3K
2
,
E
,odd-hole)-free ∩ line
(S
3
,
C
n+4
∪ K
1
,
C(n,k)
,
W
4
,even-hole,odd-cycle ∪ K
1
)-free
(S
3
,
C
n+4
∪ K
1
,
W
4
,even-hole,net,odd-cycle ∪ K
1
)-free
(S
3
,
C
n+4
,
S
3
∪ K
1
,co-claw)-free
(S
3
,
C
n+4
,
T
2
)-free
(S
3
,
C
n+4
,co-claw)-free
(S
3
,
C
n+4
,net)-free
(S
3
,
C
n+6
,
X
37
,antenna,co-claw,co-sun)-free
(S
3
,co-claw,net)-free
(S
3
,co-claw)-free
(S
3
,net)-free ∩ chordal
S
3
-free ∩ chordal
(T
2
,X
2
,X
3
,X
30
,X
31
,X
32
,X
33
,X
34
,X
35
,X
36
,XF
2
n+1
,XF
3
n
,XF
4
n
,anti-hole,co-XF
1
2n+3
,co-XF
5
2n+3
,co-XF
6
2n+2
,hole)-free
(W
4
,claw,gem,odd-hole)-free
(W
4
,claw,gem)-free
(W
4
,gem)-free
(W
4
,gem)-free ∩ short-chorded
Welsh-Powell opposition
(X
103
,
C
n+4
,
S
3
∪ K
1
,
net ∪ K
1
,co-claw,co-eiffeltower)-free
(X
12
,X
5
,X
95
,X
96
,X
97
,
X
12
,
X
5
,
X
95
,
X
96
,
X
97
,
claw ∪ triangle
,claw ∪ triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free
(X
172
,triangle)-free
(X
34
,X
36
,XF
2
n+1
,XF
3
n
,
C
n+4
,co-XF
1
2n+3
,co-XF
6
2n+2
)-free
(X
37
,diamond,even-cycle)-free
(X
38
,gem,house)-free
XC
10
-free
XC
10
-free ∩ pseudo-modular
(XC
11
,claw,diamond)-free
(XC
7
,
XC
1
,
XC
2
,
XC
3
,
XC
4
,
XC
5
,
XC
6
,
XC
8
)-free
β-perfect
β-perfect ∩ co-β-perfect
β-perfect ∩ perfect
(G)-perfect
(
3K
2
,
C
6
,
P
7
,
X
164
,
X
165
,
sunlet
4
,odd anti-cycle)-free
(
A
,
T
2
,odd anti-cycle)-free
(
C
n+4
,
H
)-free
(
C
n+4
,
T
2
,co-XF
2
n+1
)-free
(
C
n+4
,
X
59
,co-longhorn)-free
(
C
n+4
,bull,co-dart,co-gem)-free
(
C
n+4
,co-claw,co-gem)-free
(
C
n+4
,co-claw)-free
(
C
n+4
,co-diamond)-free
(
C
n+4
,co-gem)-free
(
C
n+4
,co-sun)-free
(
C
n+4
,net)-free
(
C
n+4
,odd co-sun)-free
C
n+4
-free
(
C
n+6
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
35
,
X
36
,
X
37
,
X
38
,
X
39
,
X
40
,
X
41
,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
)-free
(
C
n+6
,odd anti-cycle)-free
(
E
,
P
)-free
(
E
,odd anti-cycle)-free
(
K
1,4
,
P
,co-fork,house)-free
(
K
1,4
,house)-free
(
K
1,4
,odd anti-cycle)-free
K
2
∪ claw
-free
(
P
,
P
7
)-free
(
P
,
P
8
)-free
(
P
,
T
2
)-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
7
,
star
1,2,3
,
sunlet
4
,odd anti-cycle)-free
(
P
7
,
star
1,2,3
,odd anti-cycle)-free
(
T
3
,
X
81
,co-cycle)-free
(
T
3
,co-cycle)-free
(
W
4
,co-claw,co-gem,odd anti-hole)-free
(
W
4
,co-claw,co-gem)-free
(
W
4
,co-claw)-free
(
X
177
,odd anti-cycle)-free
(
X
82
,
X
83
,house)-free
(
XC
11
,co-claw,co-diamond)-free
(
XC
12
,co-cycle)-free
(
claw ∪ 3K
1
,odd anti-cycle)-free
(n+4)-pan
-free
(
star
1,2,3
,
sunlet
4
,odd anti-cycle)-free
(
star
1,2,3
,odd anti-cycle)-free
τ
k
-perfect for all k >= 2
absolutely perfect
absorbantly perfect
alternately colourable
alternately orientable
alternately orientable ∩ co-comparability
(anti-hole,bull,odd-hole)-free
(anti-hole,co-domino,odd anti-cycle)-free
(anti-hole,co-sun,hole)-free
(anti-hole,fork)-free
(anti-hole,hole,sun)-free
(anti-hole,hole)-free
(anti-hole,odd anti-cycle)-free
(anti-hole,odd-hole)-free
b-perfect
balanced
balanced ∩ co-line
balanced ∩ line
bar visibility
basic 4-leaf power
biclique separable
biclique-Helly
bip
*
bipartable
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
bipolarizable
bithreshold
bounded multitolerance
bounded tolerance
boxicity 1
boxicity 2
bridged
bridged ∩ clique-Helly
brittle
(bull,co-fork,co-gem)-free
(bull,co-fork)-free
(bull,co-gem,gem)-free
(bull,hole,odd anti-hole)-free
(bull,house)-free
(bull,odd anti-hole,odd-hole)-free
bull-free ∩ perfect
(butterfly,gem)-free
charming
chordal
chordal ∩ circular arc ∩ claw-free
chordal ∩ (claw,net)-free
chordal ∩ claw-free
chordal ∩ clique-Helly
chordal ∩ clique-chordal
chordal ∩ co-comparability
chordal ∩ diametral path
chordal ∩ dominating pair
chordal ∩ domination perfect
chordal ∩ dually chordal
chordal ∩ hereditary clique-Helly
chordal ∩ irredundance perfect
chordal ∩ neighbourhood perfect
chordal ∩ odd-sun-free
chordal ∩ planar
chordal ∩ sun-free
chordal ∪ co-chordal
chordal-perfect
circle
circle ∩ diamond-free
circle-polygon
circular arc
circular arc ∩ co-bipartite
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular perfect
(claw,diamond,odd-hole)-free
(claw,diamond)-free
(claw,odd anti-hole,odd-hole)-free
(claw,odd anti-hole)-free ∩ tripartite
(claw,odd-hole)-free ∩ tripartite
claw-free ∩ odd anti-hole-free ∩ tripartite
claw-free ∩ odd-hole-free ∩ tripartite
claw-free ∩ perfect
clique separable
clique-perfect ∩ triangle-free
cliquewidth 3
cliquewidth 4
co-Gallai
co-HHD-free
co-Matula perfect
co-Meyniel
co-P
4
-brittle
co-Welsh-Powell opposition
co-Welsh-Powell perfect
co-biclique separable
co-bipartite
co-bipartite ∩ normal circular arc
co-bithreshold
co-chordal
(co-claw,co-diamond,odd anti-hole)-free
(co-claw,co-diamond)-free
(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
co-comparability ∩ tolerance
co-comparability ∪ comparability
co-comparability graphs of dimension d posets
co-comparability graphs of posets of interval dimension 2
co-comparability graphs of posets of interval dimension 2, height 1
co-comparability graphs of posets of interval dimension d
(co-cricket,house)-free
co-cycle-free
(co-diamond,house)-free
(co-diamond,odd anti-hole)-free
co-forest-perfect
(co-fork,hole)-free
(co-fork,house)-free
co-fork-free
(co-gem,gem)-free
(co-gem,house)-free
co-interval ∪ interval
co-interval bigraph
co-interval containment bigraph
co-interval filament
co-interval mixed
co-line
co-line graphs of bipartite graphs
(co-odd building,odd anti-hole)-free
(co-paw,odd anti-hole)-free
co-perfectly orderable
co-probe cograph
co-strongly chordal
co-threshold tolerance
co-tolerance
cograph contraction
coin
concave-round
convex-round
(cross,triangle)-free
cycle-bicolorable
d-trapezoid
(diamond,even-cycle)-free
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
directed path
disk contact
domination
domination perfect ∩ planar
domination perfect ∩ triangle-free
domino
(domino,gem,house)-free
doubly chordal
even-cycle-free
even-hole-free ∩ probe chordal
extended P
4
-laden
forest-perfect
(fork,house)-free
gem-free
generalized strongly chordal
genus 0
geodetic
good
grid intersection
gridline
hereditary Helly
hereditary N
*
-perfect
hereditary biclique-Helly
hereditary clique-Helly
hereditary clique-Helly ∩ line ∩ perfect
hereditary clique-Helly ∩ self-clique
hereditary disk-Helly
hereditary dismantlable
hereditary dually chordal
hereditary homogeneously orderable
hereditary maximal clique irreducible
hereditary neighbourhood-Helly
hereditary open-neighbourhood-Helly
(hole,odd anti-hole)-free
homothetic triangle contact
(house,hole,domino,sun)-free
house-free ∩ weakly chordal
i-triangulated
intersection graphs of parallelograms (squares)
interval
interval filament
k-leaf power, fixed k
k-polygon
k-starlike
kernel solvable
line
line ∩ perfect
line graphs of bipartite graphs
line graphs of bipartite multigraphs
line graphs of linear hypergraphs of rank 3
line graphs of multigraphs without triangles
line graphs of triangle-free graphs
linear domino
linear domino ∩ maximum degree 4
locally perfect
max-tolerance
maximal planar
maximum degree 3
module-composed
multitolerance
murky
neighbourhood perfect
neighbourhood-Helly ∩ triangle-free
normal circular arc
odd anti-cycle-free
(odd anti-hole,odd-hole)-free
(odd building,odd-hole)-free
odd-hole-free ∩ planar
odd-hole-free ∩ pretty
odd-signable ∩ triangle-free
open-neighbourhood-Helly
opposition
overlap
parity
partial bar visibility
paw-free
perfect
perfect ∩ planar
perfect ∩ split-neighbourhood
perfectly 1-transversable
perfectly contractile
perfectly orderable
planar
planar ∩ triangle-free
planar of maximum degree 3
planar of maximum degree 4
polyhedral
power-chordal
preperfect
probe Gallai
probe HHDS-free
probe Meyniel
probe P
4
-reducible
probe P
4
-sparse
probe chordal
probe chordal ∩ weakly chordal
probe chordal bipartite
probe co-trivially perfect
probe cograph
probe distance-hereditary
probe interval
probe ptolemaic
probe split
probe strongly chordal
probe trivially perfect
probe unit interval
proper tolerance
pseudo-median
pseudo-split
quasi-Meyniel
quasi-brittle
quasi-median
quasi-parity
quasitriangulated
semi-square intersection
semiperfectly orderable
short-chorded
skeletal
slender
slightly triangulated
slim
spider graph
split-perfect
square of tree
strict quasi-parity
strong tree-cograph
strongly 3-colorable
strongly chordal
strongly circular perfect
strongly orderable
strongly perfect
sun-free ∩ weakly chordal
superperfect
threshold tolerance
tolerance
totally unimodular
trapezoid
tree-cograph
tree-perfect
triangle contact
triangle-free
triangulated
tripartite
undirected path
unimodular
unit bar visibility
unit disk
unit tolerance
very strongly perfect
weak bar visibility
weak bipolarizable
weak bisplit
weakly chordal
weakly geodetic
wing-triangulated
back to top
NP-hard
back to top
NP-complete
(2K
2
,3K
1
,C
5
,
C
6
,
C
7
,
C
8
,
H
,
K
1,4
,
X
85
)-free
(2K
2
,3K
1
,C
5
,
C
6
,
C
7
,
C
8
,
H
,
X
85
)-free
(2K
2
,3K
1
)-free
(2K
2
,4K
1
,C
5
,co-diamond)-free
(2K
2
,A,H)-free
(2K
2
,C
5
,
C
6
,net)-free
(2K
2
,C
5
)-free
(2K
2
,claw)-free
(2K
2
,co-diamond)-free
(2K
2
,net)-free
2K
2
-free
(2K
3
,2K
3
+ e,
A
,
H
,
X
45
,
XZ
5
,co-domino)-free
(2K
3
,3K
1
,
A
,
H
,
X
45
)-free
(2K
3
,X
42
,
A
,
H
,
X
45
,
X
46
,
X
47
,
X
48
,
X
49
,
X
50
,
X
51
,
X
52
,
X
53
,
X
54
,
X
55
,
X
56
,
X
57
)-free
2P
3
-free
(3K
1
,C
5
,
C
6
,
X
164
,
X
165
,
sunlet
4
)-free
(3K
1
,
C
6
)-free
(3K
1
,
H
)-free
(3K
1
,
K
1,5
)-free
(3K
1
,co-cross)-free
3K
1
-free
(3K
2
,C
5
,C
7
,P
2
∪ P
4
,X
173
,
X
11
,net)-free
(3K
2
,C
5
,P
2
∪ P
4
,net)-free
(3K
2
,E,P
2
∪ P
4
,net)-free
(4K
1
,net)-free
4K
1
-free
(5,2)
(6,1)-chordal
(6,1)-even-chordal
(A ∪ K
1
,
K
1,4
,
W
4
,
W
5
,co-4-fan,co-fork ∪ K
1
,gem ∪ K
1
,net ∪ K
1
)-free
(A,H,K
3,3
,K
3,3
-e,X
45
,XZ
5
,domino)-free
(A,H,K
3,3
,X
45
,X
46
,X
47
,X
48
,X
49
,X
50
,X
51
,X
52
,X
53
,X
54
,X
55
,X
56
,X
57
,
X
42
)-free
(A,P
6
,domino)-free
AT-free
AT-free ∩ claw-free
BW
3
-free
(C
5
,P,P
5
,
P
,bull,co-gem,fork)-free
(C
5
,P
5
)-free
C
5
-free
(C
6
,C
8
,T
2
,X
3
,
BW
3
,
W
5
,
W
7
,
X
103
,
X
105
,
X
106
,
X
107
,
X
108
,
X
109
,
X
110
,
X
111
,
X
112
,
X
113
,
X
114
,
X
115
,
X
116
,
X
117
,
X
118
,
X
119
,
X
120
,
X
121
,
X
122
,
X
123
,
X
124
,
X
125
,
X
126
,
X
53
,
X
88
,co-X
104
)-free
(C
6
,K
3,3
+e,P,P
7
,X
37
,X
41
)-free
(C
6
,
C
6
)-free
C
6
-free
CONV
(C
n+6
,T
2
,X
2
,X
3
,X
30
,X
31
,X
32
,X
33
,X
34
,X
35
,X
36
,X
37
,X
38
,X
39
,X
40
,X
41
,XF
2
n+1
,XF
3
n
,XF
4
n
)-free
(C
n+6
,X
37
,claw,co-antenna,net,sun)-free
C
n+6
-free
C
n+7
-free
(E,P)-free
E-free
Hamiltonian hereditary
(K
1,4
,P,P
5
,fork)-free
(K
1,4
,P
5
)-free
K
1,4
-free
(K
2
∪ K
3
,P
5
,
X
37
,
X
38
,co-diamond,co-domino,co-twin-C
5
)-free
(K
2
∪ K
3
,co-diamond)-free
K
2
∪ K
3
-free
K
2
∪ claw-free
(K
2,3
,P,P
5
)-free
(K
2,3
,P,hole)-free
(K
2,3
,P
5
)-free
K
2,3
-free
(K
3,3
,P
5
)-free
(K
3,3
-e,P
5
,X
98
)-free
(K
3,3
-e,P
5
,X
99
)-free
(K
3,3
-e,P
5
)-free
(K
4,4
,P
5
)-free
N
*
(P,P
5
)-free
(P,P
7
)-free
(P,P
8
)-free
(P,T
2
)-free
(P,star
1,2,3
)-free
(P,star
1,2,4
)-free
(P,star
1,2,5
)-free
P-free
P
2
∪ P
4
-free
P
4
-bipartite
(P
5
,X
82
,X
83
)-free
(P
5
,
C
6
)-free
(P
5
,
X
38
,co-gem)-free
(P
5
,bull)-free
(P
5
,claw)-free
(P
5
,co-domino,co-gem)-free
(P
5
,cricket)-free
(P
5
,fork)-free
P
5
-free
(P
6
,X
30
,X
8
)-free
P
6
-free
P
7
-free
(S
3
,S
4
,net)-free
(S
3
,claw,net)-free
(S
3
,net)-free
(S
3
,net)-free ∩ sun-free
S
3
-free
(X
30
,XZ
1
,XZ
4
,longhorn)-free
(X
79
,X
80
)-free
BW
3
-free
C
6
-free
(
K
1,4
,co-diamond)-free
(
K
1,4
,co-paw)-free
K
1,4
-free
(
P
,fork)-free
P
-free
(
W
4
,
W
5
,co-butterfly)-free
(
W
4
,co-gem)-free
(
X
30
,
XZ
1
,
XZ
4
,co-longhorn)-free
(
X
79
,
X
80
)-free
XC
10
-free
XC
11
-free
XC
12
-free
(bull,fork)-free
bull-free
(claw,net)-free
(claw,odd-hole)-free
claw-free
claw-free ∩ upper domination perfect
co-building-free
(co-butterfly,co-gem)-free
co-diamond-free
co-domino-free
co-gem-free
co-hereditary clique-Helly
co-paw-free
co-planar
co-sun-free
diametral path
dominating pair
domination perfect
domino-free
even-hole-free
even-signable
fork-free
hole-free
irredundance perfect
irredundance perfect with ir(G)<= 4
(n+4)-pan-free
nK
2
-free, fixed n
nP
3
-free, fixed n
net-free
odd co-sun-free
odd-hole-free
odd-sun-free
perfect connected-dominant
probe AT-free
string
strong domination perfect
sun-free
upper domination perfect
upper irredundance perfect
weak dominating pair
back to top
coNP-complete
back to top
Open
back to top
Unknown to ISGCI
(1,2)-colorable
1-string
(2,2)-colorable
(2,2)-interval
2-connected
2-interval
2-split
(2K
3
+ e,3K
1
,C
5
,
T
2
,
X
18
,
X
94
,co-domino)-free
(2K
3
+ e,A,C
5
,C
6
,E,H,K
3,3
-e,R,X
168
,X
171
,X
18
,X
45
,X
5
,X
58
,X
84
,X
95
,
A
,
C
6
,
E
,
H
,
R
,
X
168
,
X
171
,
X
18
,
X
45
,
X
5
,
X
58
,
X
84
,
X
95
,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-free
(2K
3
,2K
3
+ e,3K
1
,
A
,
H
,
T
2
,
X
18
,
X
45
,co-domino)-free
3-DIR
3-DIR contact
3-Helly
3-interval
3-mino
(3K
1
,C
5
,K
3
∪ K
4
,
BW
3
,
K
3,4
-e
,
T
2
,
X
18
,
X
92
,
X
93
)-free
(3K
1
,
2P
3
)-free
(3K
1
,
3K
2
)-free
(3K
1
,
P
2
∪ P
4
)-free
(3K
2
,E,net,odd anti-hole)-free
3d grid
(4-fan,K
1,4
,W
4
,W
5
,
A ∪ K
1
,
co-fork ∪ K
1
,
gem ∪ K
1
,
net ∪ K
1
)-free
(4K
1
,house)-free
(6,2)-chordal
(6,3)
(7,5)
(BW
3
,W
5
,W
7
,X
103
,X
104
,X
105
,X
106
,X
107
,X
108
,X
109
,X
110
,X
111
,X
112
,X
113
,X
114
,X
115
,X
116
,X
117
,X
118
,X
119
,X
120
,X
121
,X
122
,X
123
,X
124
,X
125
,X
126
,X
53
,X
88
,
C
6
,
C
8
,
T
2
,
X
3
)-free
Birkhoff
Bouchet
(C
5
,S
3
,X
11
,
3K
2
,
C
7
,
P
2
∪ P
4
,
X
173
)-free
(C
5
,S
3
,
3K
2
,
P
2
∪ P
4
)-free
(C
5
,house)-free
(C
6
,house)-free
CIS
EPT
Helly
Helly ∩ reflexive
PURE-k-DIR
Raspail
(S
3
,
3K
2
,
E
,odd-hole)-free
SEG
(W
4
,W
5
,butterfly)-free
(W
4
,claw)-free
X-chordal
X-conformal
3
-perfect
2P
3
-free
(
A
,
P
6
,co-domino)-free
(
C
n+3
∪ K
1
,co-diamond,co-paw)-free
C
n+6
-free
C
n+7
-free
E
-free
P
2
∪ P
4
-free
(
P
6
,
X
30
,
X
8
)-free
P
6
-free
P
7
-free
(
X
37
,co-diamond,even anti-cycle)-free
absolute reflexive retract
all-4-simplicial
anti-hole-free
balanced 2-interval
bigeodetic
biplanar
building-free
building-free ∩ even-signable
building-free ∩ odd-signable
caterpillar arboricity <= 2
(claw,odd anti-hole)-free
clique
clique-Helly
clique-Helly ∩ clique-chordal
clique-Helly ∩ dismantlable
clique-Helly ∩ dismantlable ∩ reflexive
clique-chordal
clique-perfect
co-β-perfect
co-circular perfect
(co-diamond,even anti-cycle)-free
cop-win
disk
disk-Helly
dismantlable
dually chordal
even anti-cycle-free
even anti-hole-free
frame hereditary dominating pair
genus 1
graceful
harmonious
hereditary X-chordal
hereditary weakly modular
homogeneously orderable
house-free
induced-hereditary pseudo-modular
interval enumerable
interval regular
interval regular of diameter 2
irredundance perfect with ir(G)=2
isometric-HH-free
isometric-hereditary pseudo-modular
k-DIR
line graphs of Helly hypergraphs of rank 3
linear arboricity <= 2
locally connected
maximal clique irreducible
maximum degree 4
middle
nearly bipartite
neighbourhood-Helly
neighbourhood-Helly ∩ pseudo-modular ∩ reflexive
normal
odd anti-hole-free
odd-signable
outer-string
(p,q)-colorable
(p,q<=2)-colorable
p-connected
p-tree
partial 3d grid
partial rectangle visibility
partitionable
path orderable
polar
pretty
probe co-comparability
probe comparability
probe permutation
pseudo-modular
(q,t)
quasi-line
rectangle visibility
reflexive
self-clique
split-neighbourhood
strong asteroid free
strongly even-signable
strongly odd-signable
subtree filament
subtree overlap
thickness <= 2
toroidal
unbreakable
unigraph
unit 2-interval
unit Helly circle
visibility
weak rectangle visibility
weakly modular
well covered
back to top
(G)-perfect
3-perfect