Information System on Graph Classes and their Inclusions
Find class
Global
ISGCI home
Java
All classes
References
Smallgraphs
✉
This page
Constant
Polynomial
Exponential
Factorial
superfactorial ($2^{o(n^2)}$)
superfactorial ($2^{\Theta(n^2)}$)
Open
Unknown to ISGCI
Speed
Definition:
The speed of a class $X$ is the function $n \mapsto |X_n|$, where $X_n$ is the set of $n$-vertex labeled graphs in $X$.
Constant
2K
1
-free
K
2
-free
complete
back to top
Polynomial
(2K
2
,3K
1
,P
3
)-free
(2K
2
,P
3
,triangle)-free
(3K
1
,C
4
,
P
3
)-free
(C
4
,
P
3
,triangle)-free
back to top
Exponential
(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
,3K
1
,C
4
,P
4
)-free
(2K
2
,C
4
,C
5
,S
3
,claw,net)-free
(2K
2
,C
4
,C
5
,S
3
,co-claw,net)-free
(2K
2
,C
4
,P
4
,triangle)-free
(2K
2
,P
3
)-free
(3K
1
,P
3
)-free
(C
4
,
P
3
)-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
(
P
3
,triangle)-free
bipartite ∩ bithreshold
complete split
indifference ∩ split
probe complete
back to top
Factorial
(0,2)-colorable ∩ chordal
(0,3)-colorable ∩ chordal
1-DIR
1-bounded bipartite
(2,0)-colorable ∩ chordal
2-DIR
2-bounded bipartite
2-leaf power
(2K
2
,3K
1
,C
5
,
C
6
,
C
7
,
C
8
,
H
,
K
1,4
,
X
85
)-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,C
5
,S
3
,X
159
,X
219
,
C
6
,
E
,
P
6
,
X
159
,
X
219
,
X
58
,co-rising sun,net,rising sun)-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
,claw,diamond)-free
(2K
2
,C
4
,C
5
,co-claw,co-diamond)-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
,
C
6
,
C
7
,
C
8
,
XC
11
,co-claw,co-diamond)-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
,
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
-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
(2P
3
,C
4
,P
4
)-free
(2P
3
,P
4
)-free
3-DIR
3-DIR contact
3-leaf power
(3K
1
,C
4
,C
5
)-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
,butterfly,diamond)-free
(3K
1
,P
4
)-free
(3K
1
,
K
1,5
)-free
(3K
1
,
K
2
∪ claw
)-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-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
(3K
2
,
P
,co-gem,house)-free
(4K
1
,P
4
)-free
(4K
1
,
C
n+4
)-free
(4K
1
,co-claw,co-diamond)-free
(5,1)
(5,2)-crossing-chordal
5-leaf power
(5-pan,T
2
,X
172
)-free ∩ planar
(6,2)
(6,2)-chordal ∩ bipartite
(7,3)
(7,4)
(9,6)
(A,C
5
,C
6
,E,P
6
,S
3
,X
159
,X
219
,X
5
,X
58
,
A
,
C
6
,
E
,
P
6
,
X
159
,
X
219
,
X
5
,
X
58
,antenna,co-antenna,co-domino,co-rising sun,domino,net,rising sun)-free
(A,C
5
,C
6
,E,P
6
,S
3
,X
159
,X
219
,X
58
,
A
,
X
159
,
X
219
,co-rising sun,domino,house,net,rising sun)-free
(A,C
5
,P
5
,S
3
,X
159
,X
219
,
A
,
C
6
,
E
,
P
6
,
X
159
,
X
219
,
X
58
,co-domino,co-rising sun,net,rising sun)-free
(A,T
2
,odd-cycle)-free
AC
AT-free ∩ bipartite
AT-free ∩ chordal
B
0
-VPG
B
0
-VPG ∩ bipartite
B
0
-VPG ∩ triangle-free
B
1
-CPG
B
1
-CPG ∩ triangle-free
B
1
-VCPG
(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
,C
6
,E,P
6
,S
3
,X
159
,X
219
,X
58
,
A
,
X
159
,
X
219
,co-rising sun,net,rising sun)-free
(C
4
,C
5
,K
4
,diamond)-free ∩ planar
(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
,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
,triangle)-free ∩ planar
C
4
-free ∩ co-comparability
C
4
-free ∩ galled-tree explainable
(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
,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
,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
5
,gem)-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
,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
,S
3
,
C
n+4
∪ K
1
,
W
4
,
W
5
,co-claw,net)-free
CPG
(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
,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
,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
,claw,net)-free
(C
n+4
,S
3
,claw,net)-free
(C
n+4
,T
2
,X
31
,XF
2
n+1
,XF
3
n
)-free
(C
n+4
,X
102
,X
204
,
P
3
∪ 2K
1
,gem)-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
,dart,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
(E,odd-cycle)-free
E-free ∩ bipartite
E-free ∩ planar
HHDG-free
Helly circle
(K
1,4
,odd-cycle)-free
(K
1,4
,odd-cycle)-free ∩ planar
(K
1,5
,triangle)-free
(K
2
∪ K
3
,P
4
,butterfly)-free
(K
2
∪ K
3
,
P
,
X
163
,
X
95
,co-diamond,house)-free
(K
2
∪ claw,triangle)-free
(K
2,3
,P,P
5
,X
163
,X
95
,diamond)-free
(K
2,3
,P
4
,co-butterfly)-free
(K
3
∪ 3K
1
,
C
n+4
,co-dart,co-gem)-free
(K
3,3
,K
5
)-minor-free
K
3
-minor-free
(K
4
,P
4
)-free
(K
4
,claw,diamond)-free
K
4
-free ∩ map
K
4
-free ∩ planar
K
4
-minor-free
(K
5
,X
126
,X
174
,
3K
2
)-minor-free
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
3
∪ 2K
1
,
C
n+4
,
X
102
,
X
204
,co-gem)-free
(P
3
,triangle)-free
P
3
-free
(P
4
,
2P
3
)-free
(P
4
,co-cycle)-free
(P
4
,co-diamond,co-paw)-free
(P
4
,cycle)-free
(P
4
,diamond,paw)-free
(P
4
,triangle)-free
P
4
-extendible
P
4
-extendible ∩ P
4
-sparse
P
4
-free
P
4
-free ∩ starlike
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
,anti-hole,co-domino,co-gem)-free
(P
5
,
P
,gem)-free
(P
5
,anti-hole,co-domino,co-gem)-free
(P
5
,bull,co-fork)-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
,gem)-free
(P
5
,triangle)-free
(P
6
,triangle)-free
P
6
-free ∩ chordal bipartite
(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
PURE-2-DIR
PURE-3-DIR
PURE-k-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
,
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
,co-claw,net)-free
(S
3
,claw,net)-free ∩ chordal
(S
3
,net)-free ∩ extended P
4
-sparse
SEG
(T
2
,X
2
,X
3
,hole,triangle)-free
(T
2
,X
205
,X
206
,X
207
,X
208
,even-hole,odd-cycle)-free
(T
2
,cycle)-free
(T
3
,X
81
,cycle)-free
(T
3
,cycle)-free
(X
172
,triangle)-free
(X
177
,odd-cycle)-free
(XC
11
,claw,diamond)-free
(XC
11
,odd-cycle)-free
(XC
11
,odd-cycle)-free ∩ planar
(XC
12
,cycle)-free
(XC
12
,triangle)-free
(XC
12
,triangle)-free ∩ planar
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
(
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
,
T
2
,
X
31
,co-XF
2
n+1
,co-XF
3
n
)-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-dart,co-gem)-free
(
C
n+4
,co-diamond)-free
(
C
n+4
,co-gem)-free
(
E
,odd anti-cycle)-free
(
K
1,4
,odd anti-cycle)-free
(
P
,butterfly,fork,gem)-free
(
P
,fork,gem)-free
(
P
,fork,house)-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
(
X
177
,odd anti-cycle)-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
(
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
almost tree (1)
(anti-hole,co-domino,odd anti-cycle)-free
astral triple-free
bi-cograph
biconvex
binary tree
binary tree ∩ partial grid
bipartite ∩ bounded tolerance
bipartite ∩ boxicity 2
bipartite ∩ bridged
bipartite ∩ claw-free
bipartite ∩ co-comparability
bipartite ∩ convex-round
bipartite ∩ distance-hereditary
bipartite ∩ girth >=9 ∩ maximum degree 3 ∩ planar
bipartite ∩ grid intersection
bipartite ∩ maximum degree 3
bipartite ∩ maximum degree 3 ∩ planar
bipartite ∩ maximum degree 4 ∩ planar
bipartite ∩ module-composed
bipartite ∩ planar
bipartite ∩ probe interval
bipartite ∩ tolerance
bipartite ∩ trapezoid
bipartite chain
bipartite permutation
bipartite tolerance
biplanar
block
block duplicate
boxicity 1
(bull,co-fork,co-gem)-free
(bull,co-fork,fork)-free
(bull,co-gem,gem)-free
(bull,fork,gem)-free
(bull,fork,house)-free
cactus
caterpillar
caterpillar arboricity <= 2
chordal ∩ co-chordal ∩ co-comparability ∩ comparability
chordal ∩ co-comparability
chordal ∩ cograph
chordal ∩ diamond-free
chordal ∩ distance-hereditary
chordal ∩ domino
chordal ∩ gem-free
chordal ∩ probe diamond-free
chordal ∩ proper circular arc
chordal ∩ unit circular arc
circle
circle ∩ diamond-free
circle graph with equator
circular arc ∩ cograph
circular interval
(claw ∪ 3K
1
,odd-cycle)-free
(claw,co-claw)-free
(claw,odd anti-hole)-free ∩ tripartite
(claw,odd-cycle)-free
(claw,odd-hole)-free ∩ tripartite
(claw,paw)-free
claw-free ∩ interval
claw-free ∩ normal Helly circular arc
claw-free ∩ odd anti-hole-free ∩ tripartite
claw-free ∩ odd-hole-free ∩ tripartite
clique graphs of interval
clique graphs of normal Helly circular arc
cliquewidth 2
cliquewidth 3
cliquewidth 4
cluster
co-biconvex
co-bipartite ∩ concave-round
co-bipartite ∩ normal circular arc
co-bipartite ∩ proper circular arc
co-bithreshold ∩ split
co-chordal ∩ comparability
co-chordal ∩ superperfect
(co-claw,co-cycle)-free
(co-claw,co-paw)-free
(co-claw,odd anti-cycle)-free
co-cluster
co-comparability ∩ comparability
co-cycle-free
(co-diamond,diamond)-free
(co-diamond,house)-free
(co-fork,odd anti-cycle)-free
(co-gem,gem)-free
(co-gem,house)-free
co-interval
co-interval ∩ cograph
co-interval ∩ cograph ∩ interval
co-interval ∩ interval
co-interval bigraph
(co-paw,paw)-free
(co-paw,triangle)-free
co-planar
co-probe threshold
co-proper interval bigraph
co-trivially perfect
co-trivially perfect ∩ trivially perfect
cograph
cograph ∩ interval
cograph ∩ split
coin
comparability ∩ distance-hereditary
comparability ∩ split
comparability graphs of arborescence orders
comparability graphs of dimension 2 posets
comparability graphs of semiorders
comparability graphs of series-parallel posets
comparability graphs of threshold orders
complete multipartite
containment graph of intervals
cycle-free
difference
disjoint union of stars
disk
disk contact
distance-hereditary
domination perfect ∩ planar
(domino,gem,hole,house,net)-free
(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
galled-tree explainable
galled-tree explainable ∩ house-free
genus 0
genus 1
grid intersection
hole-free ∩ planar
homogeneously representable
independent module-composed
indifference
intersection graph of nested intervals
interval
interval bigraph
k-DIR
k-polygon
line graphs of acyclic multigraphs
linear NLC-width 1
linear arboricity <= 2
linear cliquewidth 2
linear domino ∩ maximum degree 4
linear forest
linear interval
lobster
matrogenic
matroidal
maximum degree 1
maximum degree 3
maximum degree 3 ∩ planar ∩ triangle-free
maximum degree 4
maximum degree 5
maximum degree 6
maximum degree 7
(odd-cycle,star
1,2,3
,sunlet
4
)-free
(odd-cycle,star
1,2,3
)-free
odd-hole-free ∩ planar
overlap
partial 2-tree
partial 3-tree
partial 3-tree ∩ planar
partial 3d grid
partial 4-tree
partial bar visibility
partial grid
partial k-tree, fixed k
partner-limited
perfect ∩ planar
permutation
permutation ∩ split
planar
planar ∩ triangle-free
planar of maximum degree 3
planar of maximum degree 4
probe P
4
-reducible
probe P
4
-sparse
probe bipartite chain
probe block
probe co-trivially perfect ∩ probe trivially perfect
probe interval ∩ tree
probe threshold
probe threshold ∩ split
proper Helly circular arc
proper circular arc
proper interval
proper interval bigraph
ptolemaic
ptolemaic ∩ weakly geodetic
(q,q-4), fixed q
quasi-threshold
restricted block duplicate
semi-P
4
-sparse
semicircular
series-parallel
split ∩ superperfect
split ∩ threshold signed
starlike threshold
strictly chordal
superfragile
thickness <= 2
threshold
threshold signed
tolerance ∩ tree
tolerance ∩ triangle-free
toroidal
tree
treewidth 2
treewidth 3
treewidth 4
triangle contact
trivially perfect
unit Helly circular arc
unit circular arc
unit disk
unit interval
unit interval bigraph
weak bar visibility
back to top
superfactorial ($2^{o(n^2)}$)
(3K
1
,
C
6
)-free
(6,1)-chordal ∩ bipartite
(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
Bouchet
(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
,triangle)-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
,odd-cycle)-free
HHG-free
(P
5
,anti-hole,co-gem)-free
X-conformal ∩ bipartite ∩ hereditary X-chordal
(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
(
C
n+6
,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
bipartite ∩ co-perfectly orderable
bipartite ∩ weakly chordal
chordal bipartite
claw-free ∩ upper domination perfect
(co-fork,hole)-free
comparability ∩ weakly chordal
hereditary X-chordal
hereditary open-neighbourhood-Helly
hereditary perfect elimination bipartite
(hole,odd-cycle)-free
induced-hereditary pseudo-modular
probe chordal bipartite
sun-free ∩ weakly chordal
back to top
superfactorial ($2^{\Theta(n^2)}$)
(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
(2,0)-colorable
(2,1)-colorable
(2,2)-colorable
(2,2)-colorable ∩ chordal
2-split
(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
3K
1
-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
,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
(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,0)-colorable
4-colorable
(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)-chordal
(5,2)-odd-chordal
(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
5K
1
-free
(6,1)-chordal
(6,1)-even-chordal
(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
6K
1
-free
7K
1
-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,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
AT-free
AT-free ∩ claw-free
BW
3
-free
Berge
Berge ∩ bull-free
Berge ∩ claw-free
B
k
-VPG
(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
)-free
(C
4
,C
5
,T
2
)-free
(C
4
,C
5
)-free
(C
4
,P
5
)-free
(C
4
,P
6
)-free
(C
4
,odd-hole)-free
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
,P,P
5
,
P
,house)-free
(C
5
,P,P
5
,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
-free
(C
7
,odd anti-hole)-free
CONV
(C
n+4
,X
59
,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
,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
HH-free
HHD-free
HHD-free ∩ co-HHD-free
HHDA-free
HHDbicycle-free
HHP-free
Hamiltonian hereditary
Helly 2-acyclic subtree
(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
∪ 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
,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 ∩ perfect
K
5
-free
K
6
-free
K
7
-free
Meyniel
Meyniel ∩ co-Meyniel
Meyniel ∩ weakly chordal
(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
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
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
,
P
,anti-hole)-free
(P
5
,
P
2
∪ P
3
)-free
(P
5
,
P
6
,anti-hole)-free
(P
5
,
P
6
)-free
(P
5
,
P
6
)-free ∩ weakly chordal
(P
5
,
X
38
,co-gem)-free
(P
5
,anti-hole,co-bicycle,co-domino)-free
(P
5
,anti-hole,co-domino)-free
(P
5
,anti-hole)-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
,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
,claw)-free
(P
6
,hole,house)-free
(P
6
,house)-free
P
6
-free
P
7
-free
(S
3
,S
4
,net)-free
(S
3
,T
2
,X
205
,X
206
,X
207
,X
208
,
X
42
)-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
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
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
(X
91
,claw)-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
(G)-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
2n+3
-free
(
W
4
,
W
5
,co-butterfly)-free
(
W
4
,co-gem)-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
odd-cycle ∪ K
1
-free
absolutely perfect
absorbantly perfect
all-4-simplicial
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
b-perfect
b-perfect ∩ chordal
balanced
balanced ∩ paw-free
biclique separable
bipartite
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
bisplit
bisplit ∩ triangle-free
brittle
building-free
building-free ∩ even-signable
building-free ∩ odd-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
charming
chordal
chordal ∩ co-chordal
chordal ∩ irredundance perfect
circle-polygon
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
co-HHD-free
co-Meyniel
co-P
4
-brittle
co-β-perfect
co-biclique separable
co-bipartite
co-building-free
(co-butterfly,co-gem)-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
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-quasi-line
co-sun-free
cograph contraction
comparability
containment graphs
cycle-bicolorable
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
domination
domination perfect
domino-free
doubled
even anti-cycle-free
even anti-hole-free
even-cycle-free
even-hole-free
even-signable
extended P
4
-laden
fork-free
gem-free
good
hereditary Matula perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary clique-Helly
hereditary clique-Helly ∩ paw-free ∩ perfect
hereditary maximal clique irreducible
hereditary sat
(hole,odd anti-hole)-free
hole-free
house-free
house-free ∩ weakly chordal
interval filament
irredundance perfect
k-SEG
kernel solvable
locally bipartite
locally chordal
locally perfect
locally split
maxibrittle
murky
(n+4)-pan-free
nP
3
-free, fixed n
nearly bipartite
neighbourhood chordal
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 ∪ K
1
-free
odd-cycle-free
(odd-hole,paw)-free
odd-hole-free
odd-hole-free ∩ pretty
odd-signable
odd-sun-free
opposition
outer-string
(p,q<=2)-colorable
path orderable
paw-free
paw-free ∩ perfect
perfect
perfect ∩ triangle-free
perfect cochromatic
perfect connected-dominant
perfectly 1-transversable
perfectly colorable
perfectly orderable
polar
preperfect
pretty
probe (1,2)-colorable
probe AT-free
probe Meyniel
probe co-bipartite
probe co-comparability
probe comparability
probe diamond-free
probe split
pseudo-split
quasi-brittle
quasi-line
quasi-parity
quasitriangulated
rigid circuit
semiperfectly orderable
short-chorded
slim
spider graph
split
split-neighbourhood
starlike
strict quasi-parity
strictly clique irreducible
string
strong asteroid free
strong domination perfect
strongly 3-colorable
strongly circular perfect
strongly even-signable
substar
subtree filament
subtree overlap
sun-free
superbrittle
totally unimodular
triangle-free
triangulated
tripartite
universally signable
upper domination perfect
upper irredundance perfect
very strongly perfect
weak bipolarizable
weakly chordal
well-partitioned chordal
back to top
Open
back to top
Unknown to ISGCI
1-bounded tripartite
1-string
(2,2)-interval
2-SEG
2-circular arc
2-circular track
2-interval
2-thin
2-track
(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
,A,H)-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
5
,
C
6
,net)-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
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,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
,3K
1
,
A
,
H
,
X
45
)-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-circular track
3-interval
3-mino
3-track
(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
,
C
6
,
X
164
,
X
165
,
sunlet
4
)-free
(3K
1
,
2P
3
)-free
(3K
1
,
3K
2
)-free
(3K
1
,
E
)-free
(3K
1
,
H
)-free
(3K
1
,
P
2
∪ P
4
)-free
(3K
1
,co-cross)-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
,triangle)-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-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
,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
,gem)-free
(4K
1
,house)-free
(6,3)
(7,5)
(8,4)
(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,H,K
3,3
,X
45
,triangle)-free
(A,P
6
,clique wheel,domino,hole,house)-free
B
0
-CPG
B
1
-VPG
B
2
-VPG
B
3
-VPG
(BW
3
,C
5
,K
3,4
,K
3,4
-e,T
2
,X
18
,X
92
,X
93
,triangle)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,X
85
,triangle)-free
(C
4
,C
5
,C
6
,S
3
)-free
(C
4
,C
5
,K
4
,diamond)-free
(C
4
,C
6
,odd-cycle)-free
(C
4
,S
3
)-free
(C
4
,X
91
,claw)-free
(C
4
,
A
,
H
)-free
(C
4
,claw,diamond)-free
(C
4
,co-claw)-free
(C
4
,diamond)-free
(C
4
,triangle)-free
C
4
-free ∩ C
6
-free ∩ bipartite
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
,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
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
,S
3
,X
11
,
3K
2
,
C
7
,
P
2
∪ P
4
,
X
173
)-free ∩ co-line
(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
n+3
∪ K
1
,diamond,paw)-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
205
,
X
206
,
X
207
,
X
208
,
odd-cycle ∪ K
1
,even anti-hole,net)-free
(C
n+4
,H)-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
,XF
2
n+1
)-free
(C
n+4
,T
2
,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
,claw,net)-free
(C
n+4
,claw)-free
(C
n+4
,odd-sun)-free
(C
n+4
,sun)-free
D
(E,triangle)-free
(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
HHDS-free
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
(K
1,4
,diamond)-free
(K
1,4
,paw)-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
,co-diamond)-free
(K
2,3
,X
37
,X
38
,diamond,domino,house,twin-C
5
)-free
(K
2,3
,diamond)-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
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
,co-gem)-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
N
*
(P,co-fork)-free
(P
2
∪ P
4
,triangle)-free
P
4
-indifference
(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
,anti-hole,co-domino,co-sun)-free
(P
5
,co-domino,co-gem)-free
(P
5
,co-fork)-free
P
5
-free ∩ tripartite
P
6
-free ∩ tripartite
PI
PI
*
(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
,
3K
2
,
E
,odd-hole)-free ∩ line
(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
,net)-free ∩ chordal
(S
3
,net)-free ∩ split
S
3
-free ∩ chordal
(W
4
,claw,gem,odd-hole)-free
(W
4
,claw,gem)-free
(W
4
,claw)-free
(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
(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
(XC
1
,XC
2
,XC
3
,XC
4
,XC
5
,XC
6
,XC
7
,XC
8
)-free
XC
10
-free
XC
13
-free
(XC
7
,
XC
1
,
XC
2
,
XC
3
,
XC
4
,
XC
5
,
XC
6
,
XC
8
)-free
(
C
n+3
∪ K
1
,co-diamond,co-paw)-free
(
C
n+4
,
H
)-free
(
C
n+4
,
T
2
,co-XF
2
n+1
)-free
(
C
n+4
,co-claw)-free
(
C
n+4
,co-sun)-free
(
C
n+4
,net)-free
(
C
n+4
,odd co-sun)-free
(
K
1,4
,co-diamond)-free
(
K
1,4
,co-paw)-free
(
P
,fork)-free
(
W
4
,co-claw,co-gem,odd anti-hole)-free
(
W
4
,co-claw,co-gem)-free
(
W
4
,co-claw)-free
(
X
37
,co-diamond,even anti-cycle)-free
XC
10
-free
XC
13
-free
τ
k
-perfect for all k >= 2
adjoint ∩ partial directed line
alternately orientable ∩ co-comparability
balanced 2-interval
balanced ∩ chordal
balanced ∩ co-line
balanced ∩ line
basic 4-leaf power
bipartite ∩ co-trapezoid
bipartite ∩ mock threshold
bipolarizable
bitolerance
bounded bitolerance
bounded multitolerance
bounded tolerance
boxicity 2
boxicity 2 ∩ co-bipartite
(butterfly,claw)-free
chordal ∩ circular arc ∩ claw-free
chordal ∩ (claw,net)-free
chordal ∩ claw-free
chordal ∩ comparability
chordal ∩ diametral path
chordal ∩ domination perfect
chordal ∩ hereditary clique-Helly
chordal ∩ hereditary dominating pair
chordal ∩ neighbourhood perfect
chordal ∩ odd-sun-free
chordal ∩ sun-free
circle-n-gon, fixed n
circle-trapezoid
circular arc
circular arc ∩ co-bipartite
circular arc ∩ comparability
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular permutation
circular strip
circular trapezoid
(claw,diamond,odd-hole)-free
(claw,diamond)-free
claw-free ∩ mock threshold
(co-butterfly,co-claw)-free
(co-claw,co-diamond,odd anti-hole)-free
(co-claw,co-diamond)-free
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-diamond,even anti-cycle)-free
co-interval ∪ interval
co-interval containment bigraph
co-leaf power
co-line
co-line graphs of bipartite graphs
co-strongly chordal
co-tolerance
co-trapezoid
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
concave-round
containment graph of circles
containment graphs of circular arcs
convex-round
(cross,triangle)-free
cubical
d-trapezoid
(diamond,even-cycle)-free
directed line
directed path
domination perfect ∩ triangle-free
domino
(domino,gem,house)-free
(fork,house)-free
girth >=9
grid graph
grid graph ∩ maximum degree 3
gridline
hereditary Helly
hereditary N
*
-perfect
hereditary biclique-Helly
hereditary clique-Helly ∩ line ∩ perfect
hereditary disk-Helly
hereditary dually chordal
hereditary homogeneously orderable
hereditary neighbourhood-Helly
(house,hole,domino,sun)-free
intersection graphs of parallelograms (squares)
interval containment bigraph
interval enumerable
leaf power
leaf power ∩ min leaf power
leaf power ∪ min leaf power
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 domino
max-tolerance
min leaf power
mock threshold
module-composed
multitolerance
normal Helly circular arc
odd-signable ∩ triangle-free
(p,q)-colorable
(p,q)-split
pairwise compatibility
parallelepiped
penny
probe interval
probe interval bigraph
probe permutation
probe proper interval
probe unit interval
proper chordal
proper tolerance
(q,t)
rectangle intersection
reflexive
rooted directed path
semi-square intersection
split ∩ strongly chordal
strict 2-threshold
strict B
1
-VCPG
strongly chordal
strongly odd-signable
tolerance
trapezoepiped
trapezoid
triangular grid graph
undirected path
unit 2-circular arc
unit 2-circular track
unit 2-interval
unit 2-track
unit 3-circular track
unit 3-interval
unit 3-track
unit tolerance
weakly geodetic
back to top
(G)-perfect