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