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: Treewidth
Definition:
Input:
A graph
G
in this class and an integer
k
.
Output:
True iff the treewidth of
G
is at most
k
(see
bounded treewidth
).
Linear
(0,2)-colorable ∩ chordal
(2,0)-colorable ∩ chordal
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
,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
,2P
3
,C
4
,K
3
∪ P
3
,P
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
,P
4
)-free
(3K
1
,
T
2
,
X
2
,
X
3
,anti-hole)-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
(4K
1
,P
4
)-free
(5,2)-crossing-chordal
5-leaf power ∩ distance-hereditary
(6,2)
(6,2)-chordal ∩ bipartite
AC
AT-free ∩ bipartite
Apollonian network
(C
4
,P
4
,dart)-free
(C
4
,P
4
)-free
(C
5
,P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
C
5
-free ∩ P
4
-extendible
(C
n+4
,P
5
,bull)-free
(C
n+4
,P
5
,claw,gem)-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
Dilworth 1
Dilworth 2
HHDG-free
Halin
(K
2
∪ K
3
,P
4
,butterfly)-free
(K
2,3
,K
4
)-minor-free
(K
2,3
,P
4
,co-butterfly)-free
K
3
-minor-free
(K
4
,P
4
)-free
K
4
-minor-free
(K
5
,X
126
,X
174
,
3K
2
)-minor-free
P
3
-free
(P
4
,triangle)-free
P
4
-extendible ∩ P
4
-sparse
P
4
-free
P
4
-reducible
(P
5
,bull)-free ∩ interval
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
(XC
12
,cycle)-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
(
C
n+4
,bull,house)-free
P
3
-free
(
T
2
,co-cycle)-free
almost tree (1)
binary tree
binary tree ∩ partial grid
bipartite ∩ bithreshold
bipartite ∩ bounded tolerance
bipartite ∩ bridged
bipartite ∩ claw-free
bipartite ∩ co-comparability
bipartite ∩ distance-hereditary
bipartite ∩ module-composed
bipartite ∩ trapezoid
bipartite chain
bipartite permutation
bipartite tolerance
block
bounded treewidth
cactus
caterpillar
chordal ∩ co-chordal ∩ co-comparability ∩ comparability
chordal ∩ cograph
chordal ∩ diamond-free
chordal ∩ distance-hereditary
chordal ∩ domino
chordal ∩ gem-free
chordal ∩ maximal planar
circle graph with equator
circular arc ∩ cograph
(claw,odd-cycle)-free
cliquewidth 2
co-bipartite ∩ proper circular arc
co-comparability ∩ comparability
co-interval ∩ cograph
co-interval ∩ cograph ∩ interval
co-interval ∩ interval
co-probe threshold
co-proper interval bigraph
co-trivially perfect
co-trivially perfect ∩ trivially perfect
cograph
cograph ∩ interval
cograph ∩ split
comparability graphs of arborescence orders
comparability graphs of dimension 2 posets
comparability graphs of series-parallel posets
comparability graphs of threshold orders
containment graph of intervals
cycle-free
difference
distance-hereditary
(domino,gem,house)-free ∩ pseudo-modular
(domino,hole,odd-cycle)-free
domino-free ∩ modular
domishold
grid
homogeneously representable
independent module-composed
intersection graph of nested intervals
k-path graph, fixed k
k-tree, fixed k
line graphs of acyclic multigraphs
maximal outerplanar
outerplanar
partial 2-tree
partial 3-tree
partial 3-tree ∩ planar
partial 4-tree
partial k-tree, fixed k
permutation
permutation ∩ split
probe co-trivially perfect ∩ probe trivially perfect
probe interval ∩ tree
probe threshold
probe threshold ∩ split
proper interval bigraph
ptolemaic
ptolemaic ∩ weakly geodetic
quasi-threshold
semicircular
series-parallel
split ∩ threshold signed
superfragile
thick tree
threshold
threshold signed
tolerance ∩ tree
tree
treewidth 2
treewidth 3
treewidth 4
treewidth 5
trivially perfect
unit interval bigraph
back to top
Polynomial
(0,3)-colorable ∩ chordal
(1,1)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar
(1,2)-polar ∩ chordal
1-DIR
(2,2)-colorable ∩ chordal
2-connected ∩ (4-fan,C
n+4
,K
5
- e,S
3
,
H
,
K
3
∪ 2K
1
)-free
2-threshold
(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
-free ∩ probe cograph
(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
+ 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
,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
,2P
3
,C
n+4
,K
3
∪ P
3
)-free
(2K
3
,C
n+4
)-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
,paw)-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
,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
(3K
3
,C
n+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
(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
n+4
)-free
(5,1)
(5,2)-chordal
5-leaf power
(6,1)-chordal ∩ bipartite
(7,3)
(8,4)
(A,C
5
,C
6
,P
6
,domino,house)-free
(A,C
5
,P
5
,
A
,house,parachute,parapluie)-free
(A,E,S
3
,X
1
,domino,hole,house,net,rising sun)-free
(A,P
6
,clique wheel,domino,hole,house)-free
(A,
3P
3
,
C
n+4
,
P
3
∪ P
4
,
X
102
,
X
180
,
X
181
,
X
182
,
X
183
,house)-free
AT-free ∩ chordal
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
,X
17
,X
18
,X
5
,X
98
,
C
6
,
P
6
,antenna,domino)-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
,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
,
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
,
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
,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
-free ∩ P
4
-tidy
C
5
-free ∩ matrogenic
(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
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
,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
∪ 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
,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
∪ K
1
,claw,net)-free
(C
n+4
,S
3
,claw,net)-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
,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
,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
,odd-cycle)-free
Dilworth 3
EPT ∩ chordal
(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
HH-free
HHD-free
HHD-free ∩ co-HHD-free
HHDA-free
HHDS-free
HHDbicycle-free
HHG-free
HHP-free
Helly chordal
Helly chordal ∩ clique-chordal
Helly circle
Helly circular arc
Helly circular arc ∩ self-clique
(K
3,3,3
,
C
n+4
)-free
(K
3,3
,K
3,3
+e,
2P
3
,
C
n+4
)-free
(K
3,3
,
C
n+4
)-free
Meyniel ∩ co-Meyniel
Meyniel ∩ weakly chordal
P
4
-indifference
P
4
-laden
P
4
-lite
P
4
-simplicial
P
4
-sparse
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
,
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
,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
-free ∩ weakly chordal
(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
PI
PI
*
(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,net)-free
(S
3
,
C
n+4
,co-claw)-free
(S
3
,
C
n+4
,net)-free
(S
3
,claw,net)-free ∩ chordal
(S
3
,net)-free ∩ chordal
(S
3
,net)-free ∩ split
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
Welsh-Powell opposition
X-conformal ∩ bipartite ∩ hereditary X-chordal
(X
103
,
C
n+4
,
S
3
∪ K
1
,
net ∪ K
1
,co-claw,co-eiffeltower)-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
(XC
1
,XC
2
,XC
3
,XC
4
,XC
5
,XC
6
,XC
7
,XC
8
)-free
(XC
7
,
XC
1
,
XC
2
,
XC
3
,
XC
4
,
XC
5
,
XC
6
,
XC
8
)-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
β-perfect ∩ perfect
(
3K
2
,
C
6
,
P
7
,
X
164
,
X
165
,
sunlet
4
,odd anti-cycle)-free
(
C
n+4
,
H
)-free
(
C
n+4
,
T
2
,
X
31
,co-XF
2
n+1
,co-XF
3
n
)-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,house)-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
,odd anti-cycle)-free
(
T
3
,
X
81
,co-cycle)-free
(
T
3
,co-cycle)-free
(
XC
12
,co-cycle)-free
τ
k
-perfect for all k >= 2
absolutely perfect
almost CIS
alternately orientable ∩ co-comparability
(anti-hole,co-domino,odd anti-cycle)-free
(anti-hole,co-sun,hole)-free
(anti-hole,hole,sun)-free
(anti-hole,hole)-free
(anti-hole,odd anti-cycle)-free
astral triple-free
b-perfect ∩ chordal
basic 4-leaf power
biconvex
bipartite ∩ co-perfectly orderable
bipartite ∩ co-trapezoid
bipartite ∩ convex-round
bipartite ∩ probe interval
bipartite ∩ tolerance
bipartite ∩ weakly chordal
bipolarizable
bithreshold
bounded multitolerance
bounded tolerance
boxicity 1
brittle
charming
chordal
chordal ∩ circular arc ∩ claw-free
chordal ∩ (claw,net)-free
chordal ∩ claw-free
chordal ∩ clique-Helly
chordal ∩ clique-chordal
chordal ∩ co-chordal
chordal ∩ co-comparability
chordal ∩ 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 ∩ proper circular arc
chordal ∩ sun-free
chordal ∩ unit circular arc
chordal ∪ co-chordal
chordal bipartite
chordal-perfect
circle
circle ∩ diamond-free
circular arc
circular arc ∩ co-bipartite
circular arc ∩ comparability
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular permutation
claw-free ∩ interval
co-HHD-free
co-Welsh-Powell opposition
co-bipartite ∩ normal circular arc
co-bithreshold
co-bithreshold ∩ split
co-bounded tolerance
co-chordal
co-chordal ∩ comparability
co-chordal ∩ superperfect
co-comparability ∩ tolerance
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-cycle-free
co-forest-perfect
co-interval
co-interval ∪ interval
co-interval bigraph
co-interval containment bigraph
co-probe cograph
co-strongly chordal
co-threshold tolerance
co-tolerance
co-trapezoid
cograph contraction
comparability ∩ split
comparability ∩ weakly chordal
comparability graphs of posets of interval dimension 2
comparability graphs of posets of interval dimension 2, height 1
comparability graphs of semiorders
concave-round
containment graphs of circular arcs
convex
d-trapezoid
directed path
domination
doubly chordal
even-hole-free ∩ probe chordal
forest-perfect
generalized strongly chordal
good
hereditary Helly
hereditary Matula perfect
hereditary N
*
-perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary disk-Helly
hereditary dually chordal
hereditary homogeneously orderable
hereditary perfect elimination bipartite
(hole,odd-cycle)-free
(house,hole,domino,sun)-free
house-free ∩ weakly chordal
indifference
intersection graphs of parallelograms (squares)
interval
interval bigraph
interval containment bigraph
k-leaf power, fixed k
k-polygon
k-starlike
matroidal
maxibrittle
module-composed
normal circular arc
overlap
power-chordal
probe HHDS-free
probe P
4
-reducible
probe bipartite chain
probe chordal ∩ weakly chordal
probe co-trivially perfect
probe cograph
probe distance-hereditary
probe interval
probe ptolemaic
probe strongly chordal
probe trivially perfect
probe unit interval
proper Helly circular arc
proper circular arc
proper interval
proper tolerance
(q,q-4), fixed q
quasi-brittle
quasitriangulated
semiperfectly orderable
split
split ∩ strongly chordal
split ∩ superperfect
split-perfect
square of tree
strict 2-threshold
strong tree-cograph
strongly chordal
strongly orderable
sun-free ∩ weakly chordal
superbrittle
threshold tolerance
tolerance
tolerance ∩ triangle-free
trapezoid
tree-cograph
tree-perfect
triangulated
undirected path
unit Helly circular arc
unit circular arc
unit interval
unit tolerance
weak bipolarizable
weakly chordal
back to top
NP-hard
back to top
NP-complete
(0,2)-colorable
(0,3)-colorable
(1,2)-colorable
(2,0)-colorable
(2,2)-colorable
2-split
2-split ∩ perfect
(2K
3
+ e,
X
98
,house)-free
(2K
3
+ e,
X
99
,house)-free
(2K
3
+ e,house)-free
(2K
3
,2K
3
+ e,
A
,
H
,
X
45
,
XZ
5
,co-domino)-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
(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
-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,odd anti-hole,odd-hole)-free
(3K
2
,E,P
2
∪ P
4
,net)-free
(3K
2
,E,net,odd anti-hole)-free
(3K
2
,co-paw,odd anti-hole)-free
(4K
1
,C
7
,S
3
,X
175
,X
176
,X
42
,
X
36
,claw,co-antenna,net,odd anti-hole)-free
(4K
1
,net)-free
(4K
1
,odd anti-hole,odd-hole)-free
4K
1
-free
(5,2)
(5,2)-odd-chordal
(5,2)-odd-crossing-chordal
(5,2)-odd-noncrossing-chordal
(6,1)-chordal
(6,1)-even-chordal
(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
Berge
Berge ∩ bull-free
Berge ∩ claw-free
(C
5
,P
5
)-free
(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
5
-free
(C
6
,K
3,3
+e,P,P
7
,X
37
,X
41
)-free
C
6
-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
,XF
2
n+1
,XF
3
n
,XF
4
n
)-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
(C
n+6
,X
37
,claw,co-antenna,net,sun)-free
C
n+6
-free
C
n+7
-free
(E,P)-free
E-free
Gallai
Gallai-perfect
Hamiltonian hereditary
(K
1,4
,P,P
5
,fork)-free
(K
1,4
,P
5
)-free
K
1,4
-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
,
P
,anti-hole)-free
(K
2
∪ K
3
,
P
,house)-free
(K
2
∪ K
3
,house)-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
∪ P
3
,
C
6
,
P
,
P
7
,
X
37
,
X
41
)-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
(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
,odd anti-hole,odd-hole)-free
K
4
-free
K
4
-free ∩ perfect
Meyniel
(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
4
-brittle
P
4
-comparability
(P
5
,X
82
,X
83
)-free
(P
5
,
X
38
,co-gem)-free
(P
5
,bull,odd anti-hole)-free
(P
5
,bull)-free
(P
5
,claw)-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
,
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
(S
3
,
C
n+6
,
X
37
,antenna,co-claw,co-sun)-free
(S
3
,claw,net)-free
(S
3
,co-claw,net)-free
(S
3
,co-claw)-free
(S
3
,net)-free
(S
3
,net)-free ∩ sun-free
S
3
-free
(W
4
,W
5
,butterfly)-free
(W
4
,gem)-free
(W
4
,gem)-free ∩ short-chorded
(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
30
,XZ
1
,XZ
4
,longhorn)-free
(X
38
,gem,house)-free
(X
79
,X
80
)-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
(G)-perfect
2P
3
-free
(
3K
2
,odd-hole,paw)-free
(
A
,
P
6
,co-domino)-free
BW
3
-free
C
6
-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
-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
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
-free
P
2
∪ P
4
-free
(
P
6
,
X
30
,
X
8
)-free
P
6
-free
P
7
-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
(
X
82
,
X
83
,house)-free
(n+4)-pan
-free
absorbantly perfect
alternately orientable
(anti-hole,bull,odd-hole)-free
(anti-hole,odd-hole)-free
anti-hole-free
balanced
balanced ∩ paw-free
bip
*
bipartite
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
bisplit
bisplit ∩ triangle-free
building-free
building-free ∩ even-signable
(bull,co-fork)-free
(bull,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
circular perfect
(claw,net)-free
(claw,odd anti-hole,odd-hole)-free
(claw,odd anti-hole)-free
(claw,odd-hole)-free
claw-free
claw-free ∩ perfect
clique
clique separable
clique-Helly
clique-perfect
clique-perfect ∩ triangle-free
co-Gallai
co-Meyniel
co-P
4
-brittle
co-bipartite
co-building-free
(co-butterfly,co-gem)-free
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
co-comparability ∪ comparability
(co-cricket,house)-free
(co-diamond,odd anti-hole)-free
co-diamond-free
co-domino-free
(co-fork,house)-free
co-fork-free
co-gem-free
co-hereditary clique-Helly
co-interval filament
co-interval mixed
(co-odd building,odd anti-hole)-free
(co-paw,odd anti-hole)-free
co-paw-free
co-perfectly orderable
co-sun-free
comparability
containment graphs
cycle-bicolorable
diametral path
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
dominating pair
domination perfect
domino-free
even anti-hole-free
even-hole-free
even-signable
fork-free
gem-free
hereditary clique-Helly
hereditary clique-Helly ∩ paw-free ∩ perfect
hereditary maximal clique irreducible
(hole,odd anti-hole)-free
hole-free
house-free
i-triangulated
interval filament
irredundance perfect
irredundance perfect with ir(G)<= 4
kernel solvable
locally perfect
maximal clique irreducible
(n+4)-pan-free
nP
3
-free, fixed n
nearly bipartite
net-free
normal
odd anti-cycle-free
(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 ∩ pretty
odd-sun-free
outer-string
(p,q<=2)-colorable
parity
path orderable
paw-free
paw-free ∩ perfect
perfect
perfect ∩ split-neighbourhood
perfect ∩ triangle-free
perfect connected-dominant
perfectly 1-transversable
perfectly colorable
perfectly contractile
perfectly orderable
preperfect
pretty
probe AT-free
probe Gallai
probe Meyniel
probe chordal
probe co-comparability
probe comparability
probe split
quasi-Meyniel
quasi-parity
short-chorded
skeletal
slender
slim
split-neighbourhood
strict quasi-parity
string
strong asteroid free
strong domination perfect
strongly 3-colorable
strongly circular perfect
strongly even-signable
strongly perfect
subtree filament
subtree overlap
sun-free
superperfect
totally unimodular
triangle-free
tripartite
unimodular
upper domination perfect
upper irredundance perfect
very strongly perfect
weak bisplit
weak dominating pair
back to top
coNP-complete
back to top
Open
(K
3,3
,K
5
)-minor-free
coin
disk contact
genus 0
partial bar visibility
planar
triangle contact
weak bar visibility
back to top
Unknown to ISGCI
1-bounded bipartite
1-bounded tripartite
1-string
(2,2)-interval
2-DIR
2-bounded bipartite
2-connected
2-interval
2-subdivision
2-subdivision ∩ planar
2-thin
(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
,4K
1
,co-claw,co-diamond)-free
(2K
2
,A,H)-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
,
C
6
,net)-free
(2K
2
,C
5
,
T
2
)-free
(2K
2
,C
5
)-free
(2K
2
,
C
6
,odd anti-cycle)-free
(2K
2
,
P
6
)-free
(2K
2
,
X
91
,co-claw)-free
(2K
2
,claw)-free
(2K
2
,co-diamond)-free
(2K
2
,house)-free
(2K
2
,net)-free
(2K
2
,odd anti-hole)-free
2K
2
-free
(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
+ 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
,2K
3
+ e,3K
1
,
A
,
H
,
T
2
,
X
18
,
X
45
,co-domino)-free
(2K
3
,3K
1
,
A
,
H
,
X
45
)-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
(2P
3
,triangle)-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
,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
,C
5
,
C
6
,
X
164
,
X
165
,
sunlet
4
)-free
(3K
1
,C
5
,butterfly,diamond)-free
(3K
1
,
2P
3
)-free
(3K
1
,
3K
2
)-free
(3K
1
,
C
6
)-free
(3K
1
,
E
)-free
(3K
1
,
H
)-free
(3K
1
,
K
1,5
)-free
(3K
1
,
K
2
∪ claw
)-free
(3K
1
,
P
2
∪ P
4
)-free
(3K
1
,
P
6
)-free
(3K
1
,
X
172
)-free
(3K
1
,co-cross)-free
(3K
1
,co-fork)-free
(3K
1
,house)-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
,
P
,co-gem,house)-free
(3K
2
,triangle)-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
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
,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
,K
4
)-free
(4K
1
,co-claw,co-diamond)-free
(4K
1
,house)-free
(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
(6,2)-chordal
(6,3)
(7,4)
(7,5)
(9,6)
(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,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,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,T
2
,odd-cycle)-free
(BW
3
,C
5
,K
3,4
,K
3,4
-e,T
2
,X
18
,X
92
,X
93
,triangle)-free
(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
BW
3
-free ∩ modular
Birkhoff
Bouchet
(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
,C
6
,odd-cycle)-free
(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 ∩ 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
,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
5
,
P
,bull,co-gem,fork)-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
,
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-butterfly,co-diamond,triangle)-free
(C
5
,co-gem,gem)-free
(C
5
,co-gem,house)-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
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
,
C
6
)-free
(C
6
,house)-free
(C
6
,triangle)-free
C
6
-free ∩ modular
CIS
CONV
(C
n+3
∪ K
1
,diamond,paw)-free
D
Dilworth 4
(E,odd-cycle)-free
(E,triangle)-free
E-free ∩ bipartite
EPT
F
n
grid
(H,triangle)-free
Helly
Helly ∩ bridged
Helly ∩ reflexive
Hilbertian
H
n,q
grid
(K
1,4
,diamond)-free
(K
1,4
,odd-cycle)-free
(K
1,4
,paw)-free
(K
1,5
,triangle)-free
(K
2
∪ K
3
,P
5
,
X
37
,
X
38
,co-diamond,co-domino,co-twin-C
5
)-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
,
X
163
,
X
95
,co-diamond,house)-free
(K
2
∪ K
3
,co-diamond)-free
(K
2
∪ claw,triangle)-free
(K
2,3
,P,P
5
,X
163
,X
95
,diamond)-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
2,3
-free ∩ hereditary modular
(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
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
,claw,diamond)-free
(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
Matula perfect
N
*
N
*
-perfect
(P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
(P,P
5
,
3K
2
,gem)-free
(P,P
5
,
P
,co-fork,fork,house)-free
(P,P
5
,co-fork)-free
(P,
P
,co-fork,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
-extendible
P
4
-tidy
(P
5
,
C
6
)-free
(P
5
,
P
,gem)-free
(P
5
,
P
2
∪ P
3
)-free
(P
5
,bull,co-fork)-free
(P
5
,bull,house)-free
(P
5
,co-domino,co-gem)-free
(P
5
,co-fork,house)-free
(P
5
,co-fork)-free
(P
5
,diamond)-free
(P
5
,fork,house)-free
(P
5
,gem)-free
(P
5
,house)-free
(P
5
,triangle)-free
P
5
-free ∩ tripartite
(P
6
,triangle)-free
P
6
-free ∩ tripartite
(P
7
,odd-cycle,star
1,2,3
,sunlet
4
)-free
(P
7
,odd-cycle,star
1,2,3
)-free
PURE-2-DIR
PURE-3-DIR
PURE-k-DIR
Raspail
(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
,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
,net)-free ∩ extended P
4
-sparse
SEG
V-perfect
(W
4
,claw,gem,odd-hole)-free
(W
4
,claw,gem)-free
(W
4
,claw)-free
Welsh-Powell perfect
X-chordal
X-chordal ∩ X-conformal ∩ bipartite
X-chordal ∩ bipartite
X-conformal
X-conformal ∩ bipartite
X-star-chordal
(X
172
,triangle)-free
(X
177
,odd-cycle)-free
(X
37
,diamond,even-cycle)-free
(X
79
,X
80
)-free ∩ modular
XC
10
-free
XC
10
-free ∩ pseudo-modular
(XC
11
,claw,diamond)-free
XC
9
-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
β-perfect
β-perfect ∩ co-β-perfect
3
-perfect
(
A
,
T
2
,odd anti-cycle)-free
(
C
n+3
∪ K
1
,co-diamond,co-paw)-free
(
E
,odd anti-cycle)-free
(
K
1,4
,co-diamond)-free
(
K
1,4
,co-paw)-free
(
K
1,4
,odd anti-cycle)-free
(
P
,butterfly,fork,gem)-free
(
P
,fork,gem)-free
(
P
,fork,house)-free
(
P
,fork)-free
(
P
7
,
star
1,2,3
,
sunlet
4
,odd anti-cycle)-free
(
P
7
,
star
1,2,3
,odd anti-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
37
,co-diamond,even anti-cycle)-free
XC
10
-free
(
XC
11
,co-claw,co-diamond)-free
XC
11
-free
XC
12
-free
(
claw ∪ 3K
1
,odd anti-cycle)-free
(
star
1,2,3
,
sunlet
4
,odd anti-cycle)-free
(
star
1,2,3
,odd anti-cycle)-free
absolute bipartite retract
absolute reflexive retract
all-4-simplicial
alternately colourable
(anti-hole,fork)-free
b-perfect
balanced 2-interval
balanced ∩ co-line
balanced ∩ line
bar visibility
bi-cograph
biclique separable
biclique-Helly
bigeodetic
bipartable
bipartite ∩ boxicity 2
bipartite ∩ grid intersection
bipartite ∩ maximum degree 3
biplanar
boxicity 2
bridged
bridged ∩ clique-Helly
building-free ∩ odd-signable
(bull,co-fork,co-gem)-free
(bull,co-fork,fork)-free
(bull,co-gem,gem)-free
(bull,fork,gem)-free
(bull,fork,house)-free
caterpillar arboricity <= 2
circle-polygon
circular convex bipartite
(claw ∪ 3K
1
,odd-cycle)-free
(claw,co-claw)-free
(claw,diamond,odd-hole)-free
(claw,diamond)-free
(claw,odd anti-hole)-free ∩ tripartite
(claw,odd-hole)-free ∩ tripartite
(claw,paw)-free
claw-free ∩ odd anti-hole-free ∩ tripartite
claw-free ∩ odd-hole-free ∩ tripartite
claw-free ∩ upper domination perfect
clique-Helly ∩ clique-chordal
clique-Helly ∩ dismantlable
clique-Helly ∩ dismantlable ∩ reflexive
clique-chordal
cliquewidth 3
cliquewidth 4
co-Matula perfect
co-Welsh-Powell perfect
co-β-perfect
co-biclique separable
(co-claw,co-diamond,odd anti-hole)-free
(co-claw,co-diamond)-free
(co-claw,co-paw)-free
(co-claw,odd anti-cycle)-free
(co-diamond,diamond)-free
(co-diamond,even anti-cycle)-free
(co-diamond,house)-free
(co-fork,hole)-free
(co-fork,odd anti-cycle)-free
(co-gem,gem)-free
(co-gem,house)-free
co-line
co-line graphs of bipartite graphs
(co-paw,paw)-free
(co-paw,triangle)-free
co-planar
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 d
containment graph of circles
convex-round
cop-win
(cross,triangle)-free
(diamond,even-cycle)-free
disk
disk-Helly
dismantlable
domination perfect ∩ planar
domination perfect ∩ triangle-free
domino
(domino,gem,house)-free
dually chordal
even anti-cycle-free
even-cycle-free
extended P
4
-laden
extended P
4
-reducible
extended P
4
-sparse
(fork,house)-free
(fork,odd-cycle)-free
(fork,triangle)-free
frame hereditary dominating pair
genus 1
geodetic
graceful
grid intersection
gridline
half-disk Helly
harmonious
hereditary X-chordal
hereditary absolute bipartite retract
hereditary biclique-Helly
hereditary clique-Helly ∩ line ∩ perfect
hereditary clique-Helly ∩ self-clique
hereditary dismantlable
hereditary median
hereditary modular
hereditary neighbourhood-Helly
hereditary open-neighbourhood-Helly
hereditary weakly modular
homogeneously orderable
homothetic triangle contact
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
line ∩ perfect
line graphs of Helly hypergraphs of rank 3
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 arboricity <= 2
linear domino
linear domino ∩ maximum degree 4
locally connected
matrogenic
max-tolerance
maximal planar
maximum degree 3
maximum degree 4
median
middle
minimally imperfect
modular
modular ∩ open-neighbourhood-Helly
multitolerance
murky
nK
2
-free, fixed n
neighbourhood perfect
neighbourhood-Helly
neighbourhood-Helly ∩ pseudo-modular ∩ reflexive
neighbourhood-Helly ∩ triangle-free
(odd-cycle,star
1,2,3
,sunlet
4
)-free
(odd-cycle,star
1,2,3
)-free
odd-hole-free ∩ planar
odd-signable
odd-signable ∩ triangle-free
open-neighbourhood-Helly
opposition
(p,q)-colorable
p-connected
p-tree
partial 3d grid
partial grid
partial rectangle visibility
partitionable
partner-limited
perfect ∩ planar
perfect elimination bipartite
planar ∩ triangle-free
planar of maximum degree 3
planar of maximum degree 4
polar
polyhedral
probe P
4
-sparse
probe chordal bipartite
probe interval bigraph
probe permutation
pseudo-median
pseudo-modular
pseudo-modular ∩ triangle-free
pseudo-split
(q, q-3), fixed q>= 7
(q,t)
quasi-line
quasi-median
rectangle visibility
reflexive
self-clique
semi-P
4
-sparse
semi-square intersection
slightly triangulated
spider graph
strongly odd-signable
thickness <= 2
toroidal
unbreakable
unigraph
unit 2-interval
unit Helly circle
unit bar visibility
unit disk
visibility
weak rectangle visibility
weakly geodetic
weakly modular
well covered
wing-triangulated
back to top
(G)-perfect
3-perfect