ISGCI logo
Information System on Graph Classes and their Inclusions
Find class
Global
ISGCI home
Java
All classes
References
Smallgraphs
✉
This problem
Linear
Polynomial
GI-complete
NP-hard
NP-complete
coNP-complete
Open
Unknown
Problem: cutwidth decomposition
Definition:
Input: A graph
G
in this class and an integer
k
.
Output: True iff the cutwidth of
G
is at most
k
.
Linear
(2,0)-colorable ∩ chordal
2-leaf power
(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
1
-free
(2K
2
,3K
1
,C
4
,P
4
)-free
(2K
2
,3K
1
,P
3
)-free
(2K
2
,C
4
,C
5
,S
3
,claw,net)-free
(2K
2
,C
4
,P
4
,triangle)-free
(2K
2
,C
5
,triangle)-free
(2K
2
,P
3
,triangle)-free
(2K
2
,P
3
)-free
2K
2
-free ∩ bipartite
(3K
1
,C
4
,C
5
)-free
(3K
1
,C
4
,
P
3
)-free
(3K
1
,P
3
)-free
AT-free ∩ bipartite
(C
4
,
P
3
,triangle)-free
(C
n+4
,S
3
,claw,net)-free
K
2
-free
(P
3
,triangle)-free
P
3
-free
(P
4
,cycle)-free
(P
4
,triangle)-free
(S
3
,claw,net)-free ∩ chordal
(T
2
,X
2
,X
3
,hole,triangle)-free
(T
2
,cycle)-free
(
P
3
,triangle)-free
astral triple-free
bipartite ∩ bithreshold
bipartite ∩ bounded tolerance
bipartite ∩ co-comparability
bipartite ∩ trapezoid
bipartite chain
bipartite permutation
bipartite tolerance
caterpillar
chordal ∩ unit circular arc
claw-free ∩ interval
clique graphs of interval
cluster
complete
complete bipartite
difference
disjoint union of stars
half
indifference
indifference ∩ split
linear interval
maximum degree 1
proper interval
proper interval bigraph
unit interval
unit interval bigraph
back to top
Polynomial
(0,2)-colorable ∩ chordal
(2K
2
,C
4
,P
4
)-free
(C
4
,
P
3
)-free
Dilworth 1
K
3
-minor-free
(T
3
,X
81
,cycle)-free
(T
3
,cycle)-free
(XC
12
,cycle)-free
binary tree
binary tree ∩ partial grid
bipartite ∩ bridged
bounded degree ∩ bounded treewidth
co-interval ∩ cograph ∩ interval
co-trivially perfect ∩ trivially perfect
cograph ∩ split
comparability graphs of threshold orders
complete split
cycle-free
grid
linear NLC-width 1
lobster
probe complete
probe interval ∩ tree
threshold
tolerance ∩ tree
tree
back to top
GI-complete
back to top
NP-hard
back to top
NP-complete
(0,2)-colorable
(0,3)-colorable
(1,1)-colorable
(1,2)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar
(1,2)-polar ∩ chordal
(1,2)-split
1-string
(2,2)-colorable
(2,2)-colorable ∩ chordal
2-DIR
2-SEG
2-circular arc
2-circular track
2-interval
2-split
2-split ∩ perfect
2-subdivision
2-subdivision ∩ planar
2-track
(2K
2
,A,C
5
,
2P
3
,
X
170
,house)-free
(2K
2
,C
4
,C
5
)-free
(2K
2
,C
4
)-free
(2K
2
,C
5
,
C
6
,
C
7
,
C
8
)-free
(2K
2
,C
5
,
T
2
)-free
(2K
2
,C
5
)-free
(2K
2
,
2P
3
,
C
6
)-free
(2K
2
,
P
6
)-free
(2K
2
,house)-free
(2K
2
,odd anti-hole)-free
2K
2
-free
(2K
3
+ e,5-pan,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
37
,X
45
,X
5
,X
58
,X
84
,X
95
,X
98
,
5-pan
,
A
,
C
6
,
E
,
P
6
,
R
,
X
166
,
X
167
,
X
169
,
X
170
,
X
171
,
X
172
,
X
18
,
X
37
,
X
45
,
X
5
,
X
58
,
X
84
,
X
95
,
X
98
,antenna,co-antenna,co-domino,co-fish,co-twin-C
5
,co-twin-house,domino,fish,twin-C
5
,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
+ e,
X
98
,house)-free
(2K
3
+ e,
X
99
,house)-free
(2K
3
+ e,house)-free
(2K
3
,2K
3
+ e,2P
3
,C
5
,C
6
,C
7
,K
2,3
,K
3
∪ P
3
,W
4
,X
84
,X
95
,
A
,
C
6
,
P
6
,
X
5
,
X
98
,butterfly,co-domino,co-fish,fish)-free
(2K
3
,2K
3
+ e,
A
,
H
,
X
45
,
XZ
5
,co-domino)-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
(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
,C
4
,C
5
,P
5
,X
170
,
A
)-free
(2P
3
,C
4
,C
6
)-free
2P
3
-free
3-DIR
3-DIR contact
3-circular track
3-interval
3-mino
3-track
(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
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
(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-colorable
(4-fan,K
1,4
,W
4
,W
5
,
A ∪ K
1
,
co-fork ∪ K
1
,
gem ∪ K
1
,
net ∪ K
1
)-free
(5,2)
(5,2)-chordal
(5,2)-odd-chordal
(5,2)-odd-crossing-chordal
(5,2)-odd-noncrossing-chordal
5-colorable
(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
(5-pan,T
2
,X
172
)-free
(6,1)-chordal
(6,1)-even-chordal
(6,2)-chordal
6-colorable
(6-fan,C
4
∪ P
2
,C
5
,C
6
∪ K
1
,C
7
,K
2
∪ K
3
,K
2,3
,P
2
∪ P
4
,W
4
∪ K
1
,W
6
,X
132
,X
169
,X
176
,X
18
,X
197
,X
198
,X
199
,X
200
,X
201
,X
202
,X
35
,X
84
,
C
4
∪ P
2
,
C
6
∪ K
1
,
C
7
,
P
2
∪ P
4
,
W
4
∪ K
1
,
W
6
,
X
132
,
X
169
,
X
176
,
X
18
,
X
197
,
X
198
,
X
199
,
X
200
,
X
201
,
X
35
,
X
84
,
butterfly ∪ K
1
,butterfly ∪ K
1
,co-6-fan,co-fish,fish)-free
(A,C
5
,C
6
,K
2
∪ K
3
,K
3,3
,K
3,3
+e,K
3,3
-e,P
6
,X
5
,X
98
,
2P
3
,
C
6
,
C
7
,
W
4
,
X
84
,
X
95
,co-butterfly,co-fish,domino,fish)-free
(A,C
5
,C
6
,P
6
,domino,house)-free
(A,C
5
,P
5
,
A
,house,parachute,parapluie)-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,H,K
3,3
,X
45
,triangle)-free
(A,P
6
,domino)-free
(A,
3P
3
,
C
n+4
,
P
3
∪ P
4
,
X
102
,
X
180
,
X
181
,
X
182
,
X
183
,house)-free
B
0
-VPG
B
0
-VPG ∩ bipartite
B
0
-VPG ∩ triangle-free
B
1
-CPG
B
1
-CPG ∩ triangle-free
B
1
-VCPG
B
1
-VPG
B
2
-VPG
B
3
-VPG
(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
Berge
Berge ∩ bull-free
B
k
-VPG
Bouchet
(C
4
∪ P
2
,C
5
,C
6
,K
2
∪ K
3
,K
2,3
,P
6
,W
4
,X
18
,X
5
,X
84
,
C
4
∪ P
2
,
C
6
,
P
6
,
W
4
,
X
18
,
X
5
,
X
84
,antenna,co-antenna,co-domino,co-fish,domino,fish)-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
)-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 ∩ cop-win
(C
4
,P
5
)-free
(C
4
,P
6
)-free
(C
4
,S
3
)-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 ∩ odd-signable
C
4
-free ∩ perfect
(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
,C
6
,X
164
,X
165
,sunlet
4
,triangle)-free
(C
5
,P,P
5
,
P
,house)-free
(C
5
,P,P
5
,house)-free
(C
5
,P,
P
,bull,co-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
,
P
,house)-free
(C
5
,P
5
,
P
2
∪ P
3
)-free
(C
5
,P
5
,co-fish,fish,house)-free
(C
5
,P
5
,house)-free
(C
5
,P
5
)-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
(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
,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
(C
6
,
C
6
)-free murky
(C
6
,house)-free
(C
6
,triangle)-free
C
6
-free
(C
7
,odd anti-hole)-free
CONV
CPG
(C
n+4
,X
59
,longhorn)-free
C
n+4
-free
C
n+6
-free
C
n+7
-free
(E,P)-free
E-free
Gallai
Gallai-perfect
(H,triangle)-free
HH-free
HHD-free
HHD-free ∩ co-HHD-free
HHDA-free
HHDbicycle-free
HHP-free
Helly 2-acyclic subtree
K
1,4
-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
,
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
,X
37
,X
38
,diamond,domino,house,twin-C
5
)-free
(K
2,3
,diamond)-free
K
2,3
-free
(K
3
∪ 2K
1
,
K
3
∪ 2K
1
,bull,co-cricket,co-dart,cricket,dart)-free
(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
5
)-minor-free
(K
3,3
,P
5
)-free
(K
3,3
,
C
n+4
)-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 ∩ map
K
4
-free ∩ perfect
K
4
-free ∩ planar
K
5
-free
K
6
-free
K
7
-free
Matula perfect
Meyniel
Meyniel ∩ co-Meyniel
Meyniel ∩ weakly chordal
(P,P
5
)-free
(P,P
7
)-free
(P,P
8
)-free
(P,T
2
)-free
(P,co-fork)-free
(P,star
1,2,3
)-free
(P,star
1,2,4
)-free
(P,star
1,2,5
)-free
P-free
(P
2
∪ P
3
,house)-free
P
2
∪ P
4
-free
P
4
-bipartite
P
4
-brittle
P
4
-comparability
P
4
-laden
P
4
-simplicial
(P
5
,X
82
,X
83
)-free
(P
5
,
A
,anti-hole,co-domino)-free
(P
5
,
C
6
)-free
(P
5
,
C
6
)-free ∩ weakly chordal
(P
5
,
P
,anti-hole)-free
(P
5
,
P
2
∪ P
3
)-free
(P
5
,anti-hole,co-bicycle,co-domino)-free
(P
5
,anti-hole,co-domino)-free
(P
5
,anti-hole)-free
(P
5
,house)-free
P
5
-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
(P
6
,X
30
,X
8
)-free
P
6
-free
P
7
-free
PURE-2-DIR
PURE-3-DIR
PURE-k-DIR
(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
,co-claw,net)-free
(S
3
,co-claw)-free
(S
3
,net)-free
(S
3
,net)-free ∩ sun-free
S
3
-free
SEG
V-perfect
VPG
W
2n+3
-free
(W
4
,W
5
,butterfly)-free
(W
4
,X
102
,X
204
,X
209
,X
210
,X
212
,X
213
,X
214
,X
215
,X
216
,X
217
,X
218
,X
86
,
P
2
∪ P
3
,
P
3
∪ 2K
1
,
X
188
,gem)-free
(W
4
,gem)-free
(W
4
,gem)-free ∩ short-chorded
Welsh-Powell opposition
Welsh-Powell perfect
W
n+4
-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
30
,XZ
1
,XZ
4
,longhorn)-free
(X
38
,gem,house)-free
(X
42
,
T
2
,
X
205
,
X
206
,
X
207
,
X
208
,net)-free
(X
79
,X
80
)-free
XC
10
-free
(XC
11
,odd-cycle)-free
(XC
11
,odd-cycle)-free ∩ planar
XC
13
-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
β-perfect
β-perfect ∩ co-β-perfect
β-perfect ∩ perfect
cal C(G)-perfect
cal P
3
-perfect
2P
3
-free
(
3K
2
,odd-hole,paw)-free
(
5-pan
,
T
2
,
X
172
)-free
(
A
,
P
6
,co-domino)-free
BW
3
-free
C
6
-free
(
C
7
,odd-hole)-free
(
C
n+4
,
X
59
,co-longhorn)-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
-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
,co-claw)-free
P
6
-free
P
7
-free
(
W
4
,
W
5
,co-butterfly)-free
W
n+4
-free
(
X
30
,
XZ
1
,
XZ
4
,co-longhorn)-free
(
X
79
,
X
80
)-free
(
X
82
,
X
83
,house)-free
(
X
91
,co-claw)-free
(n+4)-pan
-free
absolutely perfect
absorbantly perfect
almost-split
alternately colourable
alternately orientable
alternation
(anti-hole,bull,odd-hole)-free
(anti-hole,hole)-free
(anti-hole,odd-hole)-free
anti-hole-free
apex
b-perfect
b-perfect ∩ chordal
balanced
balanced ∩ paw-free
basic perfect
biclique separable
biclique-Helly
bip
*
bipartite
bipartite ∩ boxicity 2
bipartite ∩ grid intersection
bipartite ∩ maximum degree 4 ∩ planar
bipartite ∩ planar
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ double split ∪ line graphs of bipartite graphs
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
bipartite ∪ co-bipartite ∪ split
biplanar
bisplit
bisplit ∩ triangle-free
book thickness 2
boxicity 2
bridged
brittle
building-free
building-free ∩ even-signable
building-free ∩ odd-signable
(bull,co-fork)-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 ∩ unipolar
chordal ∪ co-chordal
circle-polygon
circular perfect
clique graphs
clique separable
clique-Helly
clique-perfect
clique-perfect ∩ triangle-free
co-Gallai
co-HHD-free
co-Matula perfect
co-Meyniel
co-P
4
-brittle
co-Welsh-Powell opposition
co-Welsh-Powell perfect
co-β-perfect
co-biclique separable
co-building-free
(co-butterfly,co-claw)-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,house)-free
co-fork-free
co-interval filament
co-interval mixed
(co-odd building,odd anti-hole)-free
co-perfectly orderable
co-quasi-line
co-sun-free
co-unipolar
co-unipolar ∪ unipolar
cograph contraction
coin
comparability
containment graphs
cop-win
cubical
cycle-bicolorable
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
disk
disk contact
dismantlable
domination
domination perfect
domination perfect ∩ planar
domination perfect ∩ triangle-free
(domino,gem,house)-free
domino-free
doubled
even anti-cycle-free
even anti-hole-free
even-cycle-free
even-hole-free
even-hole-free ∩ probe chordal
even-signable
extended P
4
-laden
gem-free
generalized split
genus 0
genus 1
girth>=9
good
grid graph
grid intersection
hereditary Matula perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary biclique-Helly
hereditary clique-Helly
hereditary clique-Helly ∩ paw-free ∩ perfect
hereditary dismantlable
hereditary maximal clique irreducible
hereditary neighbourhood-Helly
hereditary open-neighbourhood-Helly
hereditary sat
hereditary weakly modular
(hole,odd anti-hole)-free
hole-free
house-free
house-free ∩ weakly chordal
i-triangulated
interval filament
irredundance perfect
irredundance perfect with ir(G)<= 4
isometric-HH-free
k-DIR
k-SEG
kernel solvable
line graphs of Helly hypergraphs of rank 3
linear arboricity <= 2
locally bipartite
locally chordal
locally perfect
locally split
map
maxibrittle
maximal clique irreducible
maximum degree 3
maximum degree 4
maximum degree 5
maximum degree 6
maximum degree 7
monopolar
murky
(n+4)-pan-free
nK
2
-free, fixed n
nP
3
-free, fixed n
nearly bipartite
neighbourhood chordal
neighbourhood-Helly
neighbourhood-Helly ∩ triangle-free
net-free
normal
(odd anti-hole,odd-hole)-free
odd anti-hole-free
(odd building,odd-hole)-free
odd co-sun-free
odd-cycle ∪ K
1
-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
(p,q<=2)-colorable
p-connected
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 cochromatic
perfect connected-dominant
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 (1,2)-colorable
probe (2,2)-colorable
probe Gallai
probe Meyniel
probe chordal
probe chordal ∩ weakly chordal
probe comparability
probe diamond-free
probe split
pseudo-split
quasi-Meyniel
quasi-brittle
quasi-parity
quasitriangulated
rectangle intersection
rectangle visibility
rigid circuit
semiperfectly orderable
short-chorded
skeletal
slender
slightly triangulated
slim
spider graph
split
split-neighbourhood
split-perfect
starlike
strict quasi-parity
strictly clique irreducible
string
strong domination perfect
strongly 3-colorable
strongly circular perfect
strongly even-signable
strongly perfect
subhamiltonian
substar
subtree filament
subtree overlap
sun-free
superbrittle
superperfect
thickness <= 2
toroidal
totally unimodular
triangle contact
triangle-free
triangulated
tripartite
unimodular
unipolar
unit 2-circular track
unit 2-track
unit 3-circular track
unit 3-track
unit disk
universally signable
upper domination perfect
upper irredundance perfect
very strongly perfect
weak bar visibility
weak bipolarizable
weak bisplit
weak rectangle visibility
weakly chordal
weakly geodetic
weakly modular
well-partitioned chordal
back to top
coNP-complete
back to top
Open
back to top
Unknown to ISGCI
(0,2)-graph
(0,2)-graph ∩ bipartite
(0,3)-colorable ∩ chordal
1-DIR
1-bounded bipartite
1-bounded tripartite
(2,0)-colorable
(2,2)-interval
2-bounded bipartite
2-connected
2-connected ∩ (4-fan,C
n+4
,K
5
- e,S
3
,
H
,
K
3
∪ 2K
1
)-free
2-connected ∩ (P
6
,claw)-free
2-connected ∩ cubic ∩ planar
2-connected ∩ linearly convex triangular grid graph
2-edge-connected
2-outerplanar
2-strongly regular
2-strongly regular ∩ planar
2-terminal series-parallel
2-thin
2-threshold
2-tree
2-tree ∩ probe interval
(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
,C
5
,
C
6
,
C
7
,
C
8
)-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
,5K
1
,C
5
,K
3
∪ 2K
1
,P
3
∪ 2K
1
,
C
6
,
C
7
,
C
8
,
K
1,4
,
K
5
- e
,claw ∪ K
1
,co-butterfly,co-cricket,co-dart,co-gem)-free
(2K
2
,A,H)-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-claw,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
,claw,diamond)-free
(2K
2
,C
4
,C
5
,co-claw,co-diamond)-free
(2K
2
,C
4
,C
5
,co-sun)-free
(2K
2
,C
4
,C
5
,sun)-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
,
C
6
,
C
7
,
C
8
,
XC
11
,co-claw,co-diamond)-free
(2K
2
,C
5
,
C
6
,net)-free
(2K
2
,K
3,3
,K
3,3
+e,P
4
,
2P
3
)-free
(2K
2
,P
4
,
2P
3
)-free
(2K
2
,P
4
,co-dart)-free
(2K
2
,P
4
,co-diamond,co-paw)-free
(2K
2
,P
4
)-free
(2K
2
,
C
6
,
C
8
,
K
1,4
,odd anti-cycle)-free
(2K
2
,
C
6
,odd anti-cycle)-free
(2K
2
,
X
91
,co-claw)-free
(2K
2
,claw)-free
(2K
2
,co-claw,co-diamond)-free
(2K
2
,co-diamond)-free
(2K
2
,net)-free
2K
2
-free ∩ probe cograph
2K
2
-free ∩ probe trivially perfect
(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,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,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,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
,2K
3
+ e,3K
1
,
A
,
H
,
T
2
,
X
18
,
X
45
,co-domino)-free
(2K
3
,2P
3
,C
4
,K
3
∪ P
3
,P
4
)-free
(2K
3
,3K
1
,
A
,
H
,
X
45
)-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
(2P
3
,C
4
,P
4
)-free
(2P
3
,P
4
)-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
3-Helly
3-leaf power
3-tree
3-tree ∩ planar
(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
,
P
6
)-free
(3K
1
,C
5
,
C
6
,
X
164
,
X
165
,
sunlet
4
)-free
(3K
1
,C
5
,butterfly,diamond)-free
(3K
1
,P
4
)-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
3
)-free
(3K
1
,
P
6
)-free
(3K
1
,
T
2
,
X
2
,
X
3
,anti-hole)-free
(3K
1
,
X
172
)-free
(3K
1
,
XC
12
)-free
(3K
1
,co-cross)-free
(3K
1
,co-fork)-free
(3K
1
,house)-free
(3K
1
,paw)-free
3K
1
-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
,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
,C
7
,P
2
∪ P
4
,X
173
,
X
11
,net)-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
5
,P
2
∪ P
4
,net)-free
(3K
2
,C
6
,P
7
,X
164
,X
165
,odd-cycle,sunlet
4
)-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
,
P
,co-gem,house)-free
(3K
2
,co-paw,odd anti-hole)-free
(3K
2
,triangle)-free
3d grid
(4,0)-colorable
(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
4-regular
4-regular ∩ hamiltonian
4-regular ∩ hamiltonian ∩ planar
4-regular ∩ planar
(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
7
,X
38
,X
39
,
K
3,3
∪ K
1
,
W
4
∪ K
1
,
W
5
,
X
86
,
X
87
,
X
88
,
X
89
,
X
90
,butterfly ∪ K
1
,diamond)-free
(4K
1
,K
4
)-free
(4K
1
,P
4
)-free
(4K
1
,
C
n+4
)-free
(4K
1
,co-claw,co-diamond)-free
(4K
1
,gem)-free
(4K
1
,house)-free
(4K
1
,net)-free
(4K
1
,odd anti-hole,odd-hole)-free
4K
1
-free
(5,1)
(5,2)-crossing-chordal
5-leaf power
5-leaf power ∩ distance-hereditary
(5-pan,T
2
,X
172
)-free ∩ planar
5-regular
5-regular ∩ hamiltonian
5-regular ∩ hamiltonian ∩ planar
5-regular ∩ planar
5K
1
-free
(6,1)-chordal ∩ bipartite
(6,2)
(6,2)-chordal ∩ bipartite
(6,3)
6K
1
-free
(7,3)
(7,4)
(7,5)
7K
1
-free
(8,4)
(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,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,P
6
,clique wheel,domino,hole,house)-free
(A,T
2
,odd-cycle)-free
AC
AT-free
AT-free ∩ chordal
AT-free ∩ claw-free
Apollonian network
B
0
-CPG
B
0
-VPG ∩ chordal
B
0
-VPG ∩ strongly chordal
(BW
3
,C
5
,K
3,4
,K
3,4
-e,T
2
,X
18
,X
92
,X
93
,triangle)-free
BW
3
-free ∩ modular
Berge ∩ claw-free
Birkhoff
(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 ∩ K
1,4
-free
(C
4
,C
5
,C
6
,C
7
,C
8
,K
1,4
,K
5
,K
5
- e,
K
3
∪ 2K
1
,
P
3
∪ 2K
1
,
claw ∪ K
1
,butterfly,cricket,dart,gem)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,K
1,4
,K
5
,K
5
- e,
K
3
∪ 2K
1
,
P
3
∪ 2K
1
,
claw ∪ K
1
,butterfly,cricket,dart,gem)-free ∩ planar
(C
4
,C
5
,C
6
,C
7
,C
8
,XC
11
,claw,diamond)-free
(C
4
,C
5
,C
6
,C
7
,C
8
)-free ∩ maximum degree 3 ∩ planar
(C
4
,C
5
)-free ∩ Helly
(C
4
,C
6
,C
8
,K
1,4
,odd-cycle)-free
(C
4
,C
6
,C
8
,K
1,4
,odd-cycle)-free ∩ planar
(C
4
,C
6
,odd-cycle)-free
(C
4
,K
4
,claw,diamond)-free
(C
4
,P
4
,dart)-free
(C
4
,P
4
,diamond,paw)-free
(C
4
,P
4
)-free
(C
4
,X
91
,claw)-free
(C
4
,claw,diamond)-free
C
4
-free ∩ C
6
-free ∩ bipartite
C
4
-free ∩ co-comparability
C
4
-free ∩ induced-hereditary pseudo-modular
(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
,C
7
,C
8
,P
8
,X
19
,X
20
,X
21
,X
22
,gem,house)-free
(C
5
,C
6
,P
6
,triangle)-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
,K
3,3
-e,T
2
,X
18
,X
94
,domino,triangle)-free
(C
5
,P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
(C
5
,P,P
5
,
P
,bull,co-gem,fork)-free
(C
5
,P,P
5
,
P
,co-fork,fork,house)-free
(C
5
,P,co-fork,fork,gem,house)-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
,gem)-free
(C
5
,S
3
,X
11
,
3K
2
,
C
7
,
P
2
∪ P
4
,
X
173
)-free ∩ co-line
(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
,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
5
-free ∩ P
4
-extendible
C
5
-free ∩ P
4
-tidy
C
5
-free ∩ matrogenic
(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
,K
2
∪ K
3
,X
37
,X
90
,
C
n+4
∪ K
1
,
T
2
,
W
n+4
,
X
31
,co-XF
2
n+1
,co-XF
3
n
,co-domino,co-twin-C
5
)-free
(C
6
,S
3
,
C
n+4
∪ K
1
,
W
4
,
W
5
,co-claw,net)-free
C
6
-free ∩ modular
CIS
(C
n+3
∪ K
1
,diamond,paw)-free
(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
,W
n+4
,X
31
,XF
2
n+1
,XF
3
n
,
C
6
,
X
37
,
X
90
,domino,twin-C
5
)-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
∪ K
1
,X
42
,
T
2
,
X
205
,
X
206
,
X
207
,
X
208
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
∪ K
1
,S
3
,W
4
,W
5
,
C
6
,claw,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
,P
5
,bull)-free
(C
n+4
,P
5
,claw,gem)-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
,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
102
,X
204
,
P
3
∪ 2K
1
,gem)-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
,
K
3
∪ 3K
1
,dart,gem)-free
(C
n+4
,bull,dart,gem)-free
(C
n+4
,claw,gem)-free
(C
n+4
,claw,net)-free
(C
n+4
,claw)-free
(C
n+4
,dart,gem)-free
(C
n+4
,diamond)-free
(C
n+4
,gem)-free
(C
n+4
,odd-sun)-free
(C
n+4
,sun)-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
,anti-hole,co-XF
1
2n+3
,co-XF
5
2n+3
,co-XF
6
2n+2
)-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
,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
,X
37
,claw,co-antenna,net,sun)-free
(C
n+6
,odd-cycle)-free
D
Delaunay
Deza
Dilworth 2
Dilworth 3
Dilworth 4
(E,odd-cycle)-free
(E,triangle)-free
E-free ∩ bipartite
E-free ∩ planar
EPT
EPT ∩ chordal
F
n
grid
Gabriel
(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
HHDG-free
HHDS-free
HHG-free
Halin
Hamilton-connected
Hamiltonian hereditary
Hamming
Helly
Helly ∩ bridged
Helly ∩ reflexive
Helly cactus subtree
Helly cactus subtree ∩ perfect
Helly chordal
Helly chordal ∩ clique-chordal
Helly circle
Helly circular arc
Helly circular arc ∩ (
C
7
,odd-hole)-free
Helly circular arc ∩ concave-round
Helly circular arc ∩ perfect
Helly circular arc ∩ quasi-line
Helly circular arc ∩ self-clique
Helly subtree
Hilbertian
H
n,q
grid
(K
1,4
,P,P
5
,fork)-free
(K
1,4
,P
5
)-free
(K
1,4
,diamond)-free
(K
1,4
,odd-cycle)-free
(K
1,4
,odd-cycle)-free ∩ planar
(K
1,4
,paw)-free
K
1,4
-free ∩ almost claw-free ∩ locally connected
K
1,4
-free ∩ well covered
(K
2
∪ K
3
,P
4
,butterfly)-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
,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
,diamond)-free ∩ weakly modular
K
2,3
-free ∩ hereditary modular
(K
3
∪ 3K
1
,
C
n+4
,co-dart,co-gem)-free
(K
3,3
∪ K
1
,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
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
,claw,diamond)-free
(K
4
,co-gem)-free
(K
4
,odd anti-hole,odd-hole)-free ∩ dually chordal
K
4
-free ∩ dually chordal ∩ perfect
K
4
-minor-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
(K
5
,X
126
,X
174
,
3K
2
)-minor-free
Laman
Laman ∩ planar
Mycielski
N
*
N
*
-perfect
NLCT-width 1
(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-gem,house)-free
(P
2
∪ P
3
,P
3
∪ 2K
1
,X
188
,X
214
,
W
4
,
X
102
,
X
204
,
X
209
,
X
210
,
X
212
,
X
213
,
X
215
,
X
216
,
X
217
,
X
218
,
X
86
,co-gem)-free
(P
2
∪ P
4
,triangle)-free
(P
3
∪ 2K
1
,
C
n+4
,
X
102
,
X
204
,co-gem)-free
(P
4
,
2P
3
)-free
(P
4
,co-cycle)-free
(P
4
,co-diamond,co-paw)-free
(P
4
,diamond,paw)-free
P
4
-extendible
P
4
-extendible ∩ P
4
-sparse
P
4
-free
P
4
-free ∩ starlike
P
4
-indifference
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
,S
3
,anti-hole,co-domino,co-gem)-free
(P
5
,
A
,
P
6
,anti clique wheel,anti-hole,co-domino)-free
(P
5
,
P
,gem)-free
(P
5
,
X
38
,co-gem)-free
(P
5
,anti-hole,co-domino,co-gem)-free
(P
5
,anti-hole,co-domino,co-sun)-free
(P
5
,anti-hole,co-gem)-free
(P
5
,bull,co-fork)-free
(P
5
,bull,house)-free
(P
5
,bull,odd anti-hole)-free
(P
5
,bull)-free
(P
5
,bull)-free ∩ interval
(P
5
,claw)-free
(P
5
,co-domino,co-gem)-free
(P
5
,co-fork,house)-free
(P
5
,co-fork)-free
(P
5
,cricket)-free
(P
5
,diamond)-free
(P
5
,fork,house)-free
(P
5
,fork)-free
(P
5
,gem)-free
(P
5
,triangle)-free
P
5
-free ∩ tripartite
(P
6
,claw)-free
(P
6
,triangle)-free
P
6
-free ∩ chordal bipartite
P
6
-free ∩ tripartite
(P
7
,odd-cycle,star
1,2,3
,sunlet
4
)-free
(P
7
,odd-cycle,star
1,2,3
)-free
(P
7
,odd-cycle)-free
P
7
-free ∩ bipartite
PI
PI
*
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
,T
2
,X
205
,X
206
,X
207
,X
208
,
C
n+4
∪ K
1
,
S
3
∪ K
1
,
X
42
,even-hole,odd-cycle ∪ K
1
)-free
(S
3
,T
2
,X
205
,X
206
,X
207
,X
208
,
X
42
)-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
,
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
(S
3
,net)-free ∩ chordal
(S
3
,net)-free ∩ extended P
4
-sparse
(S
3
,net)-free ∩ split
S
3
-free ∩ chordal
SC 2-tree
SC 3-tree
SC k-tree, fixed k
(T
2
,X
205
,X
206
,X
207
,X
208
,even-hole,odd-cycle)-free
Urquhart
(W
4
,claw,gem,odd-hole)-free
(W
4
,claw,gem)-free
(W
4
,claw)-free
X-chordal
X-chordal ∩ X-conformal
X-conformal
X-conformal ∩ bipartite ∩ hereditary X-chordal
X-star-chordal
(X
103
,
C
n+4
,
S
3
∪ K
1
,
net ∪ K
1
,co-claw,co-eiffeltower)-free
(X
172
,triangle)-free
(X
177
,odd-cycle)-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
42
,
T
2
,
X
205
,
X
206
,
X
207
,
X
208
,net)-free ∩ normal circular arc ∩ quasi-line
(X
79
,X
80
)-free ∩ modular
(X
91
,claw)-free
(XC
1
,XC
2
,XC
3
,XC
4
,XC
5
,XC
6
,XC
7
,XC
8
)-free
XC
10
-free ∩ pseudo-modular
XC
10
-free ∩ weakly modular
(XC
11
,claw,diamond)-free
(XC
12
,triangle)-free
(XC
12
,triangle)-free ∩ planar
(XC
7
,
XC
1
,
XC
2
,
XC
3
,
XC
4
,
XC
5
,
XC
6
,
XC
8
)-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
,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
,
C
6
,
P
7
,
X
164
,
X
165
,
sunlet
4
,odd anti-cycle)-free
(
A
,
T
2
,odd anti-cycle)-free
(
C
n+3
∪ K
1
,co-diamond,co-paw)-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
,bull,co-dart,co-gem)-free
(
C
n+4
,bull,house)-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-dart,co-gem)-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+6
,odd anti-cycle)-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
3
-free
(
P
7
,
star
1,2,3
,
sunlet
4
,odd anti-cycle)-free
(
P
7
,
star
1,2,3
,odd anti-cycle)-free
(
P
7
,odd anti-cycle)-free
(
T
2
,
X
205
,
X
206
,
X
207
,
X
208
,even anti-hole,odd anti-cycle)-free
(
T
2
,co-cycle)-free
(
T
3
,
X
81
,co-cycle)-free
(
T
3
,co-cycle)-free
W
2n+3
-free
(
W
4
,co-claw,co-gem,odd anti-hole)-free
(
W
4
,co-claw,co-gem)-free
(
W
4
,co-claw)-free
(
W
4
,co-gem)-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
,odd anti-cycle)-free
XC
11
-free
(
XC
12
,co-cycle)-free
XC
12
-free
XC
13
-free
(
claw ∪ 3K
1
,odd anti-cycle)-free
odd-cycle ∪ K
1
-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
absolute bipartite retract
absolute reflexive retract
all-4-simplicial
almost CIS
almost claw-free
almost median
almost tree (1)
alternately orientable ∩ co-comparability
(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,odd anti-cycle)-free
balanced 2-interval
balanced ∩ chordal
balanced ∩ co-line
balanced ∩ line
bar visibility
basic 4-leaf power
bi-cograph
biconvex
bigeodetic
binary Hamming
bipartable
bipartite ∩ claw-free
bipartite ∩ co-perfectly orderable
bipartite ∩ co-trapezoid
bipartite ∩ convex-round
bipartite ∩ cubic ∩ planar
bipartite ∩ distance-hereditary
bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar
bipartite ∩ maximum degree 3
bipartite ∩ maximum degree 3 ∩ planar
bipartite ∩ mock threshold
bipartite ∩ module-composed
bipartite ∩ probe interval
bipartite ∩ quasi-median
bipartite ∩ tolerance
bipartite ∩ unit grid intersection
bipartite ∩ weakly chordal
bipolarizable
bithreshold
bitolerance
block
block duplicate
bounded bitolerance
bounded cutwidth
bounded degree
bounded multitolerance
bounded tolerance
bounded treewidth
boxicity 1
boxicity 2 ∩ co-bipartite
bridged ∩ clique-Helly
(bull,co-fork,co-gem)-free
(bull,co-fork,fork)-free
(bull,co-gem,gem)-free
(bull,fork,gem)-free
(bull,fork,house)-free
(bull,fork)-free
(bull,hole,odd anti-hole)-free
(butterfly,claw)-free
cactus
chordal ∩ circular arc ∩ claw-free
chordal ∩ (claw,net)-free
chordal ∩ claw-free
chordal ∩ clique-Helly
chordal ∩ clique-chordal
chordal ∩ co-chordal ∩ co-comparability ∩ comparability
chordal ∩ co-comparability
chordal ∩ cograph
chordal ∩ comparability
chordal ∩ diametral path
chordal ∩ diamond-free
chordal ∩ distance-hereditary
chordal ∩ domination perfect
chordal ∩ domino
chordal ∩ dually chordal
chordal ∩ gem-free
chordal ∩ hamiltonian
chordal ∩ hamiltonian ∩ planar
chordal ∩ hereditary clique-Helly
chordal ∩ hereditary dominating pair
chordal ∩ maximal planar
chordal ∩ neighbourhood perfect
chordal ∩ odd-sun-free
chordal ∩ planar
chordal ∩ probe diamond-free
chordal ∩ proper circular arc
chordal ∩ sun-free
chordal bipartite
chordal-perfect
circle
circle ∩ diamond-free
circle graph with equator
circle-n-gon, fixed n
circle-trapezoid
circular arc
circular arc ∩ clique-Helly
circular arc ∩ co-bipartite
circular arc ∩ cograph
circular arc ∩ comparability
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular arc ∩ perfect
circular convex bipartite
circular interval
circular permutation
circular strip
circular trapezoid
(claw ∪ 3K
1
,odd-cycle)-free
(claw,co-claw)-free
(claw,diamond,odd-hole)-free
(claw,diamond)-free
(claw,net)-free
(claw,odd anti-hole,odd-hole)-free
(claw,odd anti-hole)-free
(claw,odd anti-hole)-free ∩ tripartite
(claw,odd-cycle)-free
(claw,odd-hole)-free
(claw,odd-hole)-free ∩ tripartite
(claw,paw)-free
claw-free
claw-free ∩ locally connected
claw-free ∩ mock threshold
claw-free ∩ normal Helly circular arc
claw-free ∩ odd anti-hole-free ∩ tripartite
claw-free ∩ odd-hole-free ∩ tripartite
claw-free ∩ perfect
claw-free ∩ upper domination perfect
claw-free ∩ well covered
clique graphs of Helly circular arc
clique graphs of normal Helly circular arc
clique-Helly ∩ clique-chordal
clique-Helly ∩ dismantlable
clique-Helly ∩ dismantlable ∩ reflexive
clique-chordal
cliquewidth 2
cliquewidth 3
cliquewidth 4
co-2-subdivision
co-biconvex
co-bipartite
co-bipartite ∩ concave-round
co-bipartite ∩ normal circular arc
co-bipartite ∩ proper circular arc
co-bithreshold
co-bithreshold ∩ split
co-bounded tolerance
(co-butterfly,co-gem)-free
co-chordal ∩ comparability
co-chordal ∩ superperfect
(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-cluster
co-comparability
co-comparability ∩ comparability
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 2
co-comparability graphs of posets of interval dimension d
co-cycle-free
(co-diamond,diamond)-free
(co-diamond,even anti-cycle)-free
(co-diamond,house)-free
(co-diamond,odd anti-hole)-free
co-diamond-free
co-forest-perfect
(co-fork,hole)-free
(co-fork,odd anti-cycle)-free
(co-gem,gem)-free
(co-gem,house)-free
co-gem-free
co-hereditary clique-Helly
co-interval
co-interval ∩ cograph
co-interval ∩ interval
co-interval ∪ interval
co-interval bigraph
co-interval containment bigraph
co-leaf power
co-line
co-line graphs of bipartite graphs
(co-paw,odd anti-hole)-free
(co-paw,paw)-free
(co-paw,triangle)-free
co-paw-free
co-planar
co-probe cograph
co-probe threshold
co-proper interval bigraph
co-strongly chordal
co-threshold tolerance
co-tolerance
co-trapezoid
co-trivially perfect
cograph
cograph ∩ interval
comparability ∩ distance-hereditary
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 2
comparability graphs of posets of interval dimension 2, height 3
comparability graphs of posets of interval dimension d
comparability graphs of semiorders
comparability graphs of series-parallel posets
complete Hamming
complete multipartite
concave-round
containment graph of circles
containment graph of intervals
containment graphs of circular arcs
convex
convex-round
(cross,triangle)-free
cubic
cubic ∩ hamiltonian
cubic ∩ hamiltonian ∩ planar
cubic ∩ planar
d-trapezoid
diametral path
(diamond,even-cycle)-free
directed path
disk-Helly
distance regular
distance regular of diameter 2
distance-hereditary
domino
(domino,gem,hole,house,net)-free
(domino,gem,house)-free ∩ pseudo-modular
(domino,hole,odd-cycle)-free
domino-free ∩ modular
domishold
double split
doubly chordal
dually chordal
dually chordal ∩ tripartite
edge regular
equimatchable
extended P
4
-reducible
extended P
4
-sparse
forest-perfect
(fork,house)-free
(fork,odd-cycle)-free
(fork,triangle)-free
fork-free
frame hereditary dominating pair
fully cycle extendable
fuzzy circular interval
fuzzy linear interval
generalized strongly chordal
generically minimally rigid
geodetic
graceful
grid graph ∩ maximum degree 3
gridline
half-disk Helly
hamiltonian
hamiltonian ∩ interval
hamiltonian ∩ planar
hamiltonian ∩ split
harmonious
hereditary Helly
hereditary N
*
-perfect
hereditary X-chordal
hereditary absolute bipartite retract
hereditary clique-Helly ∩ line ∩ perfect
hereditary clique-Helly ∩ self-clique
hereditary disk-Helly
hereditary dominating pair
hereditary dually chordal
hereditary homogeneously orderable
hereditary median
hereditary modular
hereditary perfect elimination bipartite
(hole,odd-cycle)-free
hole-free ∩ planar
homogeneously orderable
homogeneously representable
homothetic triangle contact
(house,hole,domino,sun)-free
hypercube
independent module-composed
induced-hereditary pseudo-modular
intersection graph of nested intervals
intersection graphs of parallelograms (squares)
interval
interval bigraph
interval containment bigraph
interval enumerable
interval regular
interval regular of diameter 2
irredundance perfect with ir(G)=2
isometric subgraph of a hypercube
isometric-hereditary pseudo-modular
k-outerplanar
k-path graph, fixed k
k-polygon
k-regular, fixed k
k-regular, fixed k>= 3
k-regular, fixed k>= 6
k-tree, fixed k
leaf power
leaf power ∩ min leaf power
leaf power ∪ min leaf power
line
line ∩ mock threshold
line ∩ perfect
line ∩ well covered
line graphs of acyclic multigraphs
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 planar cubic bipartite graphs
line graphs of triangle-free graphs
line perfect
linear cliquewidth 2
linear domino
linear domino ∩ maximum degree 4
linearly convex triangular grid graph
locally connected
locally connected ∩ maximum degree 4
locally connected ∩ maximum degree 7
locally connected ∩ triangular grid graph
matrogenic
matroidal
max-tolerance
maximal outerplanar
maximal planar
maximum degree 3 ∩ planar ∩ triangle-free
median
median ∩ planar
middle
min leaf power
minimally imperfect
mock threshold
mock threshold ∩ split
modular
modular ∩ open-neighbourhood-Helly
module-composed
multitolerance
neighbourhood perfect
neighbourhood-Helly ∩ pseudo-modular ∩ reflexive
normal Helly circular arc
normal circular arc
odd anti-cycle-free
(odd-cycle,star
1,2,3
,sunlet
4
)-free
(odd-cycle,star
1,2,3
)-free
odd-signable ∩ triangle-free
outerplanar
overlap
(p,q)-colorable
(p,q)-split
p-tree
pairwise compatibility
parallelepiped
partial 2-tree
partial 3-tree
partial 3-tree ∩ planar
partial 4-tree
partial cube
partial k-tree, fixed k
partitionable
partner-limited
path orderable
perfect elimination bipartite
permutation
permutation ∩ split
planar ∩ strongly regular
polyhedral
power-chordal
premedian
probe AT-free
probe HHDS-free
probe P
4
-reducible
probe P
4
-sparse
probe bipartite chain
probe bipartite distance-hereditary
probe block
probe chordal bipartite
probe co-bipartite
probe co-comparability
probe co-trivially perfect
probe co-trivially perfect ∩ probe trivially perfect
probe cograph
probe distance-hereditary
probe interval
probe interval bigraph
probe permutation
probe proper interval
probe ptolemaic
probe strongly chordal
probe threshold
probe threshold ∩ split
probe trivially perfect
probe unit interval
proper Helly circular arc
proper chordal
proper circular arc
proper tolerance
pseudo-median
pseudo-median ∩ triangle-free
pseudo-modular
pseudo-modular ∩ triangle-free
ptolemaic
ptolemaic ∩ weakly geodetic
(q, q-3), fixed q>= 7
(q,q-4), fixed q
(q,t)
quasi-line
quasi-median
quasi-threshold
rectagraph
reflexive
relative neighbourhood graph
restricted block duplicate
rooted directed path
self-clique
self-complementary
semi-P
4
-sparse
semi-median
semi-square intersection
semicircular
series-parallel
solid grid graph
solid triangular grid graph
split ∩ strongly chordal
split ∩ superperfect
split ∩ threshold signed
square of tree
star convex
starlike threshold
strict 2-threshold
strict B
1
-VCPG
strictly chordal
strong asteroid free
strong tree-cograph
strongly chordal
strongly odd-signable
strongly orderable
strongly regular
sun-free ∩ weakly chordal
superfragile
thick tree
threshold signed
threshold tolerance
tolerance
tolerance ∩ triangle-free
trapezoepiped
trapezoid
tree convex
tree-cograph
tree-perfect
treewidth 2
treewidth 3
treewidth 4
treewidth 5
triad convex
triangular grid graph
trivially perfect
unbreakable
undirected path
unicyclic
unigraph
unit 2-circular arc
unit 2-interval
unit 3-interval
unit Helly circle
unit Helly circular arc
unit bar visibility
unit circular arc
unit grid intersection
unit tolerance
visibility
walk regular
weak dominating pair
weakly median
well covered
well-dominated
wing-triangulated
back to top
AltStyle
によって変換されたページ
(->オリジナル)
/
アドレス:
モード:
デフォルト
音声ブラウザ
ルビ付き
配色反転
文字拡大
モバイル