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: Recognition
Definition:
Input: A graph
G
.
Output: True iff
G
is in this graph class.
Linear
(0,2)-colorable
(0,2)-colorable ∩ chordal
(1,1)-colorable
1-DIR
(2,0)-colorable ∩ chordal
2-connected
2-connected ∩ cubic ∩ planar
2-edge-connected
2-leaf power
2-terminal series-parallel
2-tree
2K
1
-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
,claw,net)-free
(2K
2
,C
4
,C
5
,S
3
,co-rising sun,net,rising 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
,P
4
)-free
2K
2
-free ∩ bipartite
2K
2
-free ∩ probe cograph
2K
2
-free ∩ probe trivially perfect
(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
(2P
3
,C
4
,C
5
,P
5
,X
170
,
A
)-free
(2P
3
,C
4
,P
4
)-free
3-leaf power
3-tree
3-tree ∩ planar
(3K
1
,C
4
,C
5
)-free
(3K
1
,
T
2
,
X
2
,
X
3
,anti-hole)-free
(3K
2
,C
4
∪ P
2
,C
5
,P
2
∪ P
4
,P
5
,S
3
,X
1
,X
46
,X
70
,
3K
2
,
C
4
∪ P
2
,
P
2
∪ P
4
,
X
1
,
X
46
,
X
70
,co-fish,co-rising sun,fish,house,net,rising sun)-free
3d grid
(4-fan,C
n+4
,K
5
- e,S
3
,X
100
,X
101
,X
102
,
H
,
K
3
∪ 2K
1
)-free
4-leaf power
4-regular
4-regular ∩ planar
(5,1)
(5,2)-crossing-chordal
(5,2)-odd-crossing-chordal
5-leaf power
5-leaf power ∩ distance-hereditary
5-regular
5-regular ∩ planar
(6,2)-chordal ∩ bipartite
(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
(7,4)
(9,6)
(A,C
5
,P
5
,
A
,house,parachute,parapluie)-free
(A,E,S
3
,X
1
,domino,hole,house,net,rising sun)-free
AC
AT-free ∩ bipartite
AT-free ∩ chordal
Apollonian network
(C
4
,P
4
)-free
(C
4
,
P
3
)-free
C
4
-free ∩ co-comparability
(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
,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
-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
,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
,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
,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
,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
,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)-free
(C
n+4
,dart,gem)-free
(C
n+4
,diamond)-free
(C
n+4
,gem)-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
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
F
n
grid
HHDA-free
HHDG-free
Halin
Helly chordal ∩ clique-chordal
Helly circular arc
Helly circular arc ∩ concave-round
Helly circular arc ∩ quasi-line
H
n,q
grid
(K
1,4
,odd-cycle)-free
(K
1,4
,odd-cycle)-free ∩ planar
(K
2,3
,K
4
)-minor-free
(K
2,3
,P
4
,co-butterfly)-free
K
2
-free
(K
3,3
,K
5
)-minor-free
K
3
-minor-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
- 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
NLCT-width 1
(P,P
5
,S
3
,
P
,co-fork,fork,house,net)-free
(P,P
5
,
P
,co-fork,fork,house)-free
(P
3
,triangle)-free
P
3
-free
(P
4
,cycle)-free
P
4
-extendible
P
4
-extendible ∩ P
4
-sparse
P
4
-free
P
4
-free ∩ starlike
P
4
-indifference
P
4
-laden
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
5
,co-fork,house)-free
P
5
-free ∩ tripartite
(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
,claw,net)-free ∩ chordal
(S
3
,net)-free ∩ extended P
4
-sparse
SC 2-tree
SC 3-tree
SC k-tree, fixed k
(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
(W
4
,claw,gem)-free
(W
4
,claw)-free
X-star-chordal
(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
11
,odd-cycle)-free
(XC
11
,odd-cycle)-free ∩ planar
(XC
12
,cycle)-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
(
3K
2
,odd-hole,paw)-free
(
C
n+4
,
T
2
,
X
31
,co-XF
2
n+1
,co-XF
3
n
)-free
C
n+4
-free
absolutely perfect
almost tree (1)
apex
astral triple-free
balanced ∩ line
balanced ∩ paw-free
bar visibility
basic 4-leaf power
biconvex
binary tree
bipartite
bipartite ∩ bounded tolerance
bipartite ∩ bridged
bipartite ∩ co-comparability
bipartite ∩ convex-round
bipartite ∩ cubic ∩ planar
bipartite ∩ distance-hereditary
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
bisplit ∩ triangle-free
block
block duplicate
boxicity 1
cactus
caterpillar
chordal
chordal ∩ circular arc ∩ claw-free
chordal ∩ claw-free
chordal ∩ co-chordal
chordal ∩ co-chordal ∩ co-comparability ∩ comparability
chordal ∩ co-comparability
chordal ∩ cograph
chordal ∩ comparability
chordal ∩ diamond-free
chordal ∩ distance-hereditary
chordal ∩ domino
chordal ∩ dually chordal
chordal ∩ gem-free
chordal ∩ maximal planar
chordal ∩ planar
chordal ∩ probe diamond-free
chordal ∩ proper circular arc
chordal ∩ unit circular arc
chordal ∪ co-chordal
circle graph with equator
circular arc
circular arc ∩ cograph
circular interval
circular permutation
(claw,diamond,odd-hole)-free
claw-free ∩ interval
claw-free ∩ normal Helly circular arc
clique graphs of Helly circular arc
clique graphs of interval
clique graphs of normal Helly circular arc
clique-Helly ∩ clique-chordal
cliquewidth 2
cluster
co-bipartite ∩ proper circular arc
co-chordal
co-chordal ∩ comparability
co-chordal ∩ superperfect
co-comparability ∩ comparability
co-forest-perfect
co-interval
co-interval ∩ cograph
co-interval ∩ cograph ∩ interval
co-interval ∩ interval
co-interval ∪ interval
co-proper interval bigraph
co-trivially perfect
co-trivially perfect ∩ trivially perfect
cograph
cograph ∩ interval
cograph ∩ split
coin
comparability ∩ distance-hereditary
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
complete Hamming
complete bipartite
complete split
concave-round
containment graph of intervals
containment graphs of circular arcs
convex
convex-round
cubic
cubic ∩ planar
cycle-free
difference
disjoint union of stars
disk contact
distance-hereditary
domino
(domino,gem,hole,house,net)-free
(domino,gem,house)-free ∩ pseudo-modular
(domino,hole,odd-cycle)-free
domino-free ∩ modular
doubled
doubly chordal
dually chordal
extended P
4
-laden
extended P
4
-reducible
extended P
4
-sparse
forest-perfect
genus 0
grid
gridline
hereditary clique-Helly ∩ line ∩ perfect
hereditary clique-Helly ∩ paw-free ∩ perfect
hypercube
independent module-composed
indifference
indifference ∩ split
intersection graph of nested intervals
interval
k-path graph, fixed k
k-regular, fixed k
k-regular, fixed k>= 3
k-regular, fixed k>= 6
k-tree, fixed k
line
line graphs of acyclic multigraphs
line graphs of bipartite graphs
line graphs of multigraphs without triangles
linear NLC-width 1
linear interval
matrogenic
matroidal
maximal outerplanar
maximal planar
maximum degree 1
maximum degree 3
maximum degree 4
maximum degree 5
maximum degree 6
maximum degree 7
median ∩ planar
middle
minimally imperfect
normal Helly circular arc
odd-cycle-free
(odd-hole,paw)-free
outerplanar
p-connected
p-tree
parity
partial 2-tree
partial bar visibility
partial directed line
partial k-tree, fixed k
partner-limited
paw-free ∩ perfect
perfect ∩ triangle-free
perfectly colorable
permutation
permutation ∩ split
planar
planar of maximum degree 3
planar of maximum degree 4
probe block
probe co-trivially perfect
probe co-trivially perfect ∩ probe trivially perfect
probe cograph
probe complete
probe interval ∩ tree
probe proper interval
probe threshold
probe threshold ∩ split
probe trivially perfect
probe unit interval
proper Helly circular arc
proper circular arc
proper interval
proper interval bigraph
pseudo-split
ptolemaic
ptolemaic ∩ weakly geodetic
(q, q-3), fixed q>= 7
quasi-threshold
reflexive
rigid circuit
rooted directed path
semi-P
4
-sparse
series-parallel
split
split ∩ threshold signed
split-perfect
star convex
starlike
starlike threshold
strict 2-threshold
strictly chordal
superbrittle
threshold
threshold signed
tolerance ∩ triangle-free
tree
tree convex
tree-perfect
treewidth 2
triangle contact
triangulated
trivially perfect
unicyclic
unigraph
unit Helly circular arc
unit circular arc
unit interval
unit interval bigraph
weak bar visibility
weak bipolarizable
back to top
Polynomial
(0,2)-graph
(0,2)-graph ∩ bipartite
(0,3)-colorable ∩ chordal
(1,2)-colorable
(1,2)-colorable ∩ chordal
(1,2)-polar
(1,2)-polar ∩ chordal
1-bounded bipartite
1-bounded tripartite
(2,0)-colorable
(2,2)-colorable
(2,2)-colorable ∩ chordal
2-bounded bipartite
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-outerplanar
2-split
2-split ∩ perfect
2-strongly regular
2-strongly regular ∩ planar
2-threshold
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
4
,P
4
)-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
,C
5
,
C
6
,
C
7
,
C
8
)-free
(2K
2
,3K
1
,P
3
)-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,C
5
,
2P
3
,
X
170
,house)-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
,co-claw,net)-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
4
,P
4
,triangle)-free
(2K
2
,C
5
,
C
6
,
C
7
,
C
8
,
XC
11
,co-claw,co-diamond)-free
(2K
2
,C
5
,
C
6
,
C
7
,
C
8
)-free
(2K
2
,C
5
,
C
6
,net)-free
(2K
2
,C
5
,
T
2
)-free
(2K
2
,C
5
)-free
(2K
2
,K
3,3
,K
3,3
+e,P
4
,
2P
3
)-free
(2K
2
,P
3
,triangle)-free
(2K
2
,P
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
,
2P
3
,
C
6
)-free
(2K
2
,
C
6
,
C
8
,
K
1,4
,odd anti-cycle)-free
(2K
2
,
C
6
,odd anti-cycle)-free
(2K
2
,
P
6
)-free
(2K
2
,
X
91
,co-claw)-free
(2K
2
,claw)-free
(2K
2
,co-claw,co-diamond)-free
(2K
2
,co-diamond)-free
(2K
2
,house)-free
(2K
2
,net)-free
(2K
2
,odd anti-hole)-free
2K
2
-free
(2K
3
+ e,3K
1
,C
5
,
T
2
,
X
18
,
X
94
,co-domino)-free
(2K
3
+ e,A,C
5
,C
6
,E,H,K
3,3
-e,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
+ 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,3K
1
,
A
,
H
,
T
2
,
X
18
,
X
45
,co-domino)-free
(2K
3
,2K
3
+ e,
A
,
H
,
X
45
,
XZ
5
,co-domino)-free
(2K
3
,2P
3
,C
4
,K
3
∪ P
3
,P
4
)-free
(2K
3
,2P
3
,C
5
,C
6
,C
7
,K
2,3
,K
3
∪ P
3
,X
84
,
3K
2
,
C
4
∪ P
2
,
C
6
,
P
2
∪ P
4
,
P
6
,
X
18
,
X
5
,co-antenna,co-domino,co-fish)-free
(2K
3
,2P
3
,C
n+4
,K
3
∪ P
3
)-free
(2K
3
,3K
1
,
A
,
H
,
X
45
)-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
,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
,C
6
)-free
(2P
3
,P
4
)-free
(2P
3
,triangle)-free
2P
3
-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-mino
(3K
1
,C
4
,
P
3
)-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
,
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
3
)-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
,
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
,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
,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
(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-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
,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,2)
(5,2)-chordal
(5,2)-odd-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
(5-pan,T
2
,X
172
)-free
(5-pan,T
2
,X
172
)-free ∩ planar
5K
1
-free
(6,1)-chordal ∩ bipartite
(6,2)
(6,3)
6K
1
-free
(7,3)
(7,5)
7K
1
-free
(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,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,H,K
3,3
,K
3,3
-e,T
2
,X
18
,X
45
,domino,triangle)-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
,clique wheel,domino,hole,house)-free
(A,P
6
,domino)-free
(A,T
2
,odd-cycle)-free
(A,
3P
3
,
C
n+4
,
P
3
∪ P
4
,
X
102
,
X
180
,
X
181
,
X
182
,
X
183
,house)-free
AT-free
AT-free ∩ claw-free
B
1
-CPG ∩ triangle-free
(BW
3
,C
5
,K
3,4
,K
3,4
-e,T
2
,X
18
,X
92
,X
93
,triangle)-free
(BW
3
,W
5
,W
7
,X
103
,X
104
,X
105
,X
106
,X
107
,X
108
,X
109
,X
110
,X
111
,X
112
,X
113
,X
114
,X
115
,X
116
,X
117
,X
118
,X
119
,X
120
,X
121
,X
122
,X
123
,X
124
,X
125
,X
126
,X
53
,X
88
,
C
6
,
C
8
,
T
2
,
X
3
)-free
BW
3
-free
BW
3
-free ∩ modular
Berge
Berge ∩ bull-free
Berge ∩ claw-free
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,K
1,4
,X
85
,triangle)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,X
85
,triangle)-free
(C
4
,C
5
,C
6
,C
7
,C
8
,H,X
85
,triangle)-free ∩ K
1,4
-free
(C
4
,C
5
,C
6
,C
7
,C
8
,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
(C
4
,C
5
,C
6
,C
7
,C
8
)-free ∩ maximum degree 3 ∩ planar
(C
4
,C
5
,C
6
,S
3
)-free
(C
4
,C
5
,K
4
,diamond)-free
(C
4
,C
5
,K
4
,diamond)-free ∩ planar
(C
4
,C
5
,T
2
)-free
(C
4
,C
5
)-free
(C
4
,C
5
)-free ∩ Helly
(C
4
,C
5
)-free ∩ cop-win
(C
4
,C
6
,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
5
)-free
(C
4
,P
6
)-free
(C
4
,S
3
)-free
(C
4
,X
91
,claw)-free
(C
4
,
A
,
H
)-free
(C
4
,
P
3
,triangle)-free
(C
4
,claw,diamond)-free
(C
4
,co-claw)-free
(C
4
,diamond)-free
(C
4
,odd-hole)-free
(C
4
,triangle)-free
(C
4
,triangle)-free ∩ planar
C
4
-free
C
4
-free ∩ C
6
-free ∩ bipartite
C
4
-free ∩ induced-hereditary pseudo-modular
C
4
-free ∩ odd-signable
C
4
-free ∩ perfect
(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
,C
6
,P
6
,triangle)-free
(C
5
,C
6
,X
164
,X
165
,sunlet
4
,triangle)-free
(C
5
,K
3,3
-e,T
2
,X
18
,X
94
,domino,triangle)-free
(C
5
,P,P
5
,
P
,bull,co-gem,fork)-free
(C
5
,P,P
5
,
P
,house)-free
(C
5
,P,P
5
,house)-free
(C
5
,P,
P
,bull,co-fork,gem,house)-free
(C
5
,P,co-fork,fork,gem,house)-free
(C
5
,P
2
∪ P
3
,house)-free
(C
5
,P
5
,
A
,
C
6
,
P
6
,co-domino)-free
(C
5
,P
5
,
C
6
,
C
7
,
C
8
,
P
8
,
X
19
,
X
20
,
X
21
,
X
22
,co-gem)-free
(C
5
,P
5
,
P
,co-fork,co-gem,fork)-free
(C
5
,P
5
,
P
,house)-free
(C
5
,P
5
,
P
2
∪ P
3
)-free
(C
5
,P
5
,co-fish,fish,house)-free
(C
5
,P
5
,gem)-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
,X
11
,
3K
2
,
C
7
,
P
2
∪ P
4
,
X
173
)-free ∩ co-line
(C
5
,S
3
,
3K
2
,
P
2
∪ P
4
)-free
(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
,house)-free
C
5
-free
C
5
-free ∩ P
4
-extendible
C
5
-free ∩ P
4
-tidy
(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
,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
,S
3
,
C
n+4
∪ K
1
,
W
4
,
W
5
,co-claw,net)-free
(C
6
,
C
6
)-free
(C
6
,
C
6
)-free murky
(C
6
,house)-free
(C
6
,triangle)-free
C
6
-free
C
6
-free ∩ modular
(C
7
,odd anti-hole)-free
(C
n+4
∪ K
1
,K
2,3
,T
2
,
C
6
,
X
103
,
X
37
,
X
88
,
X
90
,diamond,domino,eiffeltower,net ∪ K
1
,twin-C
5
)-free
(C
n+4
∪ K
1
,K
2,3
,T
2
,
X
90
,domino,paw,twin-C
5
)-free
(C
n+4
,H)-free
(C
n+4
,K
4
)-free
(C
n+4
,P
5
,bull)-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
,X
59
,longhorn)-free
(C
n+4
,
K
3
∪ 3K
1
,dart,gem)-free
(C
n+4
,claw,net)-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
,X
37
,claw,co-antenna,net,sun)-free
(C
n+6
,odd-cycle)-free
D
Delaunay
Deza
Dilworth 3
Dilworth 4
(E,P)-free
(E,odd-cycle)-free
(E,triangle)-free
E-free
E-free ∩ bipartite
E-free ∩ planar
Gallai
(H,K
3
∪ 2K
1
,
C
n+4
,
K
5
- e
,
X
100
,
X
101
,
X
102
,co-4-fan,net)-free
(H,K
3
∪ 2K
1
,
C
n+4
,
K
5
- e
,co-4-fan,net)-free
(H,triangle)-free
HH-free
HHD-free
HHD-free ∩ co-HHD-free
HHDS-free
HHDbicycle-free
HHG-free
HHP-free
Hamiltonian hereditary
Hamming
Helly
Helly 2-acyclic subtree
Helly ∩ bridged
Helly ∩ reflexive
Helly cactus subtree
Helly cactus subtree ∩ perfect
Helly chordal
Helly circle
Helly circular arc ∩ (
C
7
,odd-hole)-free
Helly circular arc ∩ perfect
Hilbertian
(K
1,4
,P,P
5
,fork)-free
(K
1,4
,P
5
)-free
(K
1,4
,diamond)-free
(K
1,4
,paw)-free
K
1,4
-free
K
1,4
-free ∩ almost claw-free ∩ locally connected
(K
1,5
,triangle)-free
(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
11
,X
127
,X
128
,X
129
,X
131
,X
133
,X
135
,X
136
,X
137
,X
138
,X
139
,X
140
,X
141
,X
142
,X
143
,X
144
,X
145
,X
146
,X
147
,X
148
,X
149
,X
150
,X
151
,X
30
,X
35
,X
46
,XF
1
2n+3
,XF
6
2n+3
,
2P
3
,
3K
2
,
C
4
∪ P
2
,
C
6
,
P
6
,
X
130
,
X
132
,
X
134
,
X
152
,
X
153
,
X
154
,
X
155
,
X
156
,
X
157
,
X
158
,
X
18
,
X
84
,antenna,co-domino,co-fish,eiffeltower,longhorn,odd-hole)-free
(K
2
∪ K
3
,X
90
,
C
n+4
∪ K
1
,
T
2
,co-domino,co-paw,co-twin-C
5
)-free
(K
2
∪ K
3
,
P
,
X
163
,
X
95
,co-diamond,house)-free
(K
2
∪ K
3
,
P
,anti-hole)-free
(K
2
∪ K
3
,
P
,house)-free
(K
2
∪ K
3
,co-diamond)-free
(K
2
∪ K
3
,house)-free
K
2
∪ K
3
-free
(K
2
∪ claw,triangle)-free
K
2
∪ claw-free
(K
2,3
,P,P
5
,X
163
,X
95
,diamond)-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
,diamond)-free ∩ weakly modular
K
2,3
-free
K
2,3
-free ∩ hereditary modular
(K
3
∪ 2K
1
,
K
3
∪ 2K
1
,bull,co-cricket,co-dart,cricket,dart)-free
(K
3
∪ 3K
1
,
C
n+4
,co-dart,co-gem)-free
(K
3
∪ P
3
,
C
6
,
P
,
P
7
,
X
37
,
X
41
)-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
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
,P
4
)-free
(K
4
,P
5
)-free
(K
4
,S
3
,X
36
,
C
7
,
X
175
,
X
176
,
X
42
,antenna,co-claw,net,odd-hole)-free
(K
4
,S
3
)-free
(K
4
,claw,diamond)-free
(K
4
,co-gem)-free
(K
4
,odd anti-hole,odd-hole)-free
(K
4
,odd anti-hole,odd-hole)-free ∩ dually chordal
K
4
-free
K
4
-free ∩ dually chordal ∩ perfect
K
4
-free ∩ map
K
4
-free ∩ perfect
K
4
-free ∩ planar
(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
K
5
-free
K
6
-free
K
7
-free
Laman
Laman ∩ planar
Matula perfect
Meyniel
Meyniel ∩ co-Meyniel
Meyniel ∩ weakly chordal
N
*
N
*
-perfect
(P,P
5
,
3K
2
,gem)-free
(P,P
5
,co-fork)-free
(P,P
5
)-free
(P,P
7
)-free
(P,P
8
)-free
(P,T
2
)-free
(P,
P
,co-fork,fork)-free
(P,co-butterfly,co-fork,co-gem)-free
(P,co-fork,co-gem)-free
(P,co-fork)-free
(P,co-gem,house)-free
(P,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
,triangle)-free
P
2
∪ P
4
-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
,triangle)-free
P
4
-brittle
P
4
-comparability
P
4
-lite
P
4
-simplicial
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
,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
(P
5
,
C
6
)-free ∩ weakly chordal
(P
5
,
P
,anti-hole)-free
(P
5
,
P
,gem)-free
(P
5
,
P
2
∪ P
3
)-free
(P
5
,
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,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)-free
(P
5
,cricket)-free
(P
5
,diamond)-free
(P
5
,fork,house)-free
(P
5
,fork)-free
(P
5
,gem)-free
(P
5
,house)-free
(P
5
,triangle)-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
,triangle)-free
P
6
-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
P
7
-free ∩ bipartite
(S
3
,S
4
,net)-free
(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
,
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+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
,
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 ∩ chordal
(S
3
,net)-free ∩ split
(S
3
,net)-free ∩ sun-free
S
3
-free
S
3
-free ∩ chordal
(T
3
,cycle)-free
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
,claw,gem,odd-hole)-free
(W
4
,gem)-free
Welsh-Powell opposition
Welsh-Powell perfect
W
n+4
-free
X-chordal
X-chordal ∩ X-conformal
X-conformal
X-conformal ∩ bipartite ∩ hereditary X-chordal
(X
103
,
C
n+4
,
S
3
∪ K
1
,
net ∪ K
1
,co-claw,co-eiffeltower)-free
(X
12
,X
5
,X
95
,X
96
,X
97
,
X
12
,
X
5
,
X
95
,
X
96
,
X
97
,
claw ∪ triangle
,claw ∪ triangle,co-cricket,co-twin-house,cricket,odd anti-hole,odd-hole,twin-house)-free
(X
172
,triangle)-free
(X
177
,odd-cycle)-free
(X
30
,XZ
1
,XZ
4
,longhorn)-free
(X
34
,X
36
,XF
2
n+1
,XF
3
n
,
C
n+4
,co-XF
1
2n+3
,co-XF
6
2n+2
)-free
(X
37
,diamond,even-cycle)-free
(X
38
,gem,house)-free
(X
42
,
T
2
,
X
205
,
X
206
,
X
207
,
X
208
,net)-free
(X
79
,X
80
)-free
(X
79
,X
80
)-free ∩ modular
(X
91
,claw)-free
XC
10
-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
13
-free
(XC
7
,
XC
1
,
XC
2
,
XC
3
,
XC
4
,
XC
5
,
XC
6
,
XC
8
)-free
(XF
1
2n+3
,XF
5
2n+3
,XF
6
2n+2
,
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
(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
cal C(G)-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
2P
3
-free
(
3K
2
,
C
6
,
P
7
,
X
164
,
X
165
,
sunlet
4
,odd anti-cycle)-free
(
5-pan
,
T
2
,
X
172
)-free
(
A
,
P
6
,co-domino)-free
(
A
,
T
2
,odd anti-cycle)-free
BW
3
-free
C
6
-free
(
C
7
,odd-hole)-free
(
C
n+4
,
H
)-free
(
C
n+4
,
T
2
,co-XF
2
n+1
)-free
(
C
n+4
,
X
59
,co-longhorn)-free
(
C
n+4
,bull,co-dart,co-gem)-free
(
C
n+4
,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
,
T
2
,
X
2
,
X
3
,
X
30
,
X
31
,
X
32
,
X
33
,
X
34
,
X
35
,
X
36
,
X
37
,
X
38
,
X
39
,
X
40
,
X
41
,co-XF
2
n+1
,co-XF
3
n
,co-XF
4
n
)-free
(
C
n+6
,odd anti-cycle)-free
(
E
,
P
)-free
(
E
,odd anti-cycle)-free
E
-free
(
K
1,4
,
P
,co-fork,house)-free
(
K
1,4
,co-diamond)-free
(
K
1,4
,co-paw)-free
(
K
1,4
,house)-free
(
K
1,4
,odd anti-cycle)-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
,butterfly,fork,gem)-free
(
P
,co-star
1,2,4
)-free
(
P
,co-star
1,2,5
)-free
(
P
,fork,gem)-free
(
P
,fork,house)-free
(
P
,fork)-free
(
P
,house)-free
P
-free
P
2
∪ P
4
-free
(
P
3
,triangle)-free
P
3
-free
(
P
6
,
X
30
,
X
8
)-free
(
P
6
,co-claw)-free
P
6
-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
P
7
-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
,
W
5
,co-butterfly)-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
W
n+4
-free
(
X
177
,odd anti-cycle)-free
(
X
30
,
XZ
1
,
XZ
4
,co-longhorn)-free
(
X
37
,co-diamond,even anti-cycle)-free
(
X
79
,
X
80
)-free
(
X
82
,
X
83
,house)-free
(
X
91
,co-claw)-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
adjoint
adjoint ∩ partial directed line
almost claw-free
almost-split
alternately colourable
alternately orientable
alternately orientable ∩ co-comparability
(anti-hole,bull,odd-hole)-free
(anti-hole,co-domino,odd anti-cycle)-free
(anti-hole,fork)-free
(anti-hole,hole)-free
(anti-hole,odd anti-cycle)-free
(anti-hole,odd-hole)-free
anti-hole-free
b-perfect
b-perfect ∩ chordal
balanced
balanced ∩ chordal
balanced ∩ co-line
bi-cograph
biclique separable
biclique-Helly
binary Hamming
bipartable
bipartite ∩ bithreshold
bipartite ∩ claw-free
bipartite ∩ co-perfectly orderable
bipartite ∩ co-trapezoid
bipartite ∩ girth>=9 ∩ maximum degree 3 ∩ planar
bipartite ∩ mock threshold
bipartite ∩ quasi-median
bipartite ∩ weakly chordal
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ line graphs of bipartite graphs
bipartite ∪ co-bipartite ∪ split
bipolarizable
bisplit
bithreshold
bounded bitolerance
bounded multitolerance
bridged
bridged ∩ clique-Helly
brittle
building-free
building-free ∩ even-signable
building-free ∩ odd-signable
(bull,co-fork,co-gem)-free
(bull,co-fork,fork)-free
(bull,co-fork)-free
(bull,co-gem,gem)-free
(bull,fork,gem)-free
(bull,fork,house)-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,claw)-free
(butterfly,gem)-free
charming
chordal ∩ (claw,net)-free
chordal ∩ clique-Helly
chordal ∩ diametral path
chordal ∩ domination perfect
chordal ∩ hereditary clique-Helly
chordal ∩ hereditary dominating pair
chordal ∩ irredundance perfect
chordal ∩ neighbourhood perfect
chordal ∩ odd-sun-free
chordal ∩ sun-free
chordal ∩ unipolar
chordal bipartite
circle
circle ∩ diamond-free
circular arc ∩ clique-Helly
circular arc ∩ co-bipartite
circular arc ∩ comparability
circular arc ∩ diamond-free
circular arc ∩ paw-free
circular arc ∩ perfect
(claw ∪ 3K
1
,odd-cycle)-free
(claw,co-claw)-free
(claw,diamond)-free
(claw,net)-free
(claw,odd anti-hole,odd-hole)-free
(claw,odd anti-hole)-free
(claw,odd-cycle)-free
(claw,odd-hole)-free
(claw,paw)-free
claw-free
claw-free ∩ locally connected
claw-free ∩ mock threshold
claw-free ∩ perfect
claw-free ∩ well covered
clique separable
clique-Helly
clique-Helly ∩ dismantlable
clique-Helly ∩ dismantlable ∩ reflexive
cliquewidth 3
co-Gallai
co-HHD-free
co-Matula perfect
co-Meyniel
co-P
4
-brittle
co-Welsh-Powell opposition
co-Welsh-Powell perfect
co-biclique separable
co-biconvex
co-bipartite
co-bipartite ∩ concave-round
co-bipartite ∩ normal circular arc
co-bithreshold
co-bithreshold ∩ split
co-building-free
(co-butterfly,co-claw)-free
(co-butterfly,co-gem)-free
(co-claw,co-diamond,odd anti-hole)-free
(co-claw,co-diamond)-free
(co-claw,co-paw)-free
(co-claw,house)-free
(co-claw,odd anti-cycle)-free
(co-claw,odd anti-hole,odd-hole)-free
(co-claw,odd anti-hole)-free
(co-claw,odd-hole)-free
co-claw-free
co-cluster
co-comparability
co-comparability ∪ comparability
co-comparability graphs of posets of interval dimension 2
co-comparability graphs of posets of interval dimension 2, height 2
(co-cricket,house)-free
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-domino-free
(co-fork,hole)-free
(co-fork,house)-free
(co-fork,odd anti-cycle)-free
co-fork-free
(co-gem,gem)-free
(co-gem,house)-free
co-gem-free
co-hereditary clique-Helly
co-interval bigraph
co-interval containment bigraph
co-line
co-line graphs of bipartite graphs
(co-odd building,odd anti-hole)-free
(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-quasi-line
co-strongly chordal
co-threshold tolerance
co-trapezoid
co-unipolar
co-unipolar ∪ unipolar
cograph contraction
comparability
comparability ∩ split
comparability ∩ weakly chordal
comparability graphs of posets of interval dimension 2
comparability graphs of posets of interval dimension 2, height 2
complete multipartite
containment graphs
cop-win
(cross,triangle)-free
cycle-bicolorable
(diamond,even-cycle)-free
(diamond,odd-hole)-free
diamond-free
diamond-free ∩ perfect
directed line
directed path
disk-Helly
dismantlable
distance regular
distance regular of diameter 2
domination perfect
domination perfect ∩ planar
domination perfect ∩ triangle-free
(domino,gem,house)-free
domino-free
domishold
dually chordal ∩ tripartite
edge regular
equimatchable
even anti-cycle-free
even-cycle-free
even-hole-free ∩ probe chordal
(fork,house)-free
(fork,odd-cycle)-free
(fork,triangle)-free
fork-free
fuzzy circular interval
fuzzy linear interval
gem-free
generalized split
generalized strongly chordal
generically minimally rigid
genus 1
geodetic
girth>=9
good
half-disk Helly
hereditary Helly
hereditary Matula perfect
hereditary N
*
-perfect
hereditary V-perfect
hereditary Welsh-Powell opposition
hereditary Welsh-Powell perfect
hereditary absolute bipartite retract
hereditary biclique-Helly
hereditary clique-Helly
hereditary disk-Helly
hereditary dismantlable
hereditary dually chordal
hereditary homogeneously orderable
hereditary maximal clique irreducible
hereditary median
hereditary modular
hereditary neighbourhood-Helly
hereditary open-neighbourhood-Helly
hereditary perfect elimination bipartite
hereditary sat
(hole,odd anti-hole)-free
(hole,odd-cycle)-free
hole-free
hole-free ∩ planar
homogeneously orderable
homogeneously representable
(house,hole,domino,sun)-free
house-free
house-free ∩ weakly chordal
i-triangulated
interval bigraph
interval containment bigraph
interval regular
interval regular of diameter 2
isometric subgraph of a hypercube
isometric-hereditary pseudo-modular
k-outerplanar
k-polygon
kernel solvable
line ∩ mock threshold
line ∩ perfect
line ∩ well covered
line graphs of Helly hypergraphs of rank 3
line graphs of bipartite multigraphs
line graphs of linear hypergraphs of rank 3
line graphs of triangle-free graphs
linear cliquewidth 2
linear domino
linear domino ∩ maximum degree 4
lobster
locally bipartite
locally chordal
locally connected
locally connected ∩ maximum degree 4
locally connected ∩ maximum degree 7
locally split
maxibrittle
maximal clique irreducible
maximum degree 3 ∩ planar ∩ triangle-free
median
mock threshold
mock threshold ∩ split
modular
modular ∩ open-neighbourhood-Helly
module-composed
murky
nK
2
-free, fixed n
nP
3
-free, fixed n
nearly bipartite
neighbourhood chordal
neighbourhood-Helly
neighbourhood-Helly ∩ pseudo-modular ∩ reflexive
neighbourhood-Helly ∩ triangle-free
net-free
odd anti-cycle-free
(odd anti-hole,odd-hole)-free
odd anti-hole-free
(odd building,odd-hole)-free
odd-cycle ∪ K
1
-free
(odd-cycle,star
1,2,3
,sunlet
4
)-free
(odd-cycle,star
1,2,3
)-free
odd-hole-free
odd-hole-free ∩ planar
odd-hole-free ∩ pretty
odd-signable
odd-signable ∩ triangle-free
open-neighbourhood-Helly
overlap
partial 3-tree
partial 3-tree ∩ planar
partial 4-tree
partial cube
paw-free
perfect
perfect ∩ planar
perfect ∩ split-neighbourhood
perfect cochromatic
perfect connected-dominant
perfect elimination bipartite
perfectly 1-transversable
planar ∩ strongly regular
planar ∩ triangle-free
premedian
pretty
probe P
4
-reducible
probe P
4
-sparse
probe bipartite chain
probe bipartite distance-hereditary
probe chordal
probe chordal ∩ weakly chordal
probe co-bipartite
probe diamond-free
probe distance-hereditary
probe interval
probe interval bigraph
probe ptolemaic
probe split
proper chordal
pseudo-median
pseudo-median ∩ triangle-free
pseudo-modular
pseudo-modular ∩ triangle-free
(q,q-4), fixed q
quasi-Meyniel
quasi-adjoint
quasi-brittle
quasi-line
quasi-median
quasitriangulated
rectagraph
restricted block duplicate
semi-median
semicircular
semiperfectly orderable
slightly triangulated
split ∩ strongly chordal
split ∩ superperfect
split-neighbourhood
square of tree
strictly clique irreducible
strong asteroid free
strong tree-cograph
strongly 3-colorable
strongly chordal
strongly even-signable
strongly odd-signable
strongly orderable
strongly regular
superfragile
threshold tolerance
tolerance ∩ tree
toroidal
totally unimodular
trapezoid
tree-cograph
treewidth 3
treewidth 4
treewidth 5
triangle-free
unbreakable
undirected path
unipolar
very strongly perfect
weakly chordal
weakly geodetic
weakly median
weakly modular
well-dominated
well-partitioned chordal
wing-triangulated
back to top
GI-complete
self-complementary
back to top
NP-hard
2-SEG
disk
unit disk
back to top
NP-complete
(0,3)-colorable
2-DIR
2-interval
2-track
3-DIR
3-interval
3-track
(4,0)-colorable
4-colorable
5-colorable
6-colorable
B
0
-CPG
B
0
-VPG
B
0
-VPG ∩ bipartite
B
1
-CPG
B
1
-VPG
B
2
-VPG
B
3
-VPG
B
k
-VPG
CONV
CPG
EPT
EPT ∩ chordal
P
4
-bipartite
PI
*
PURE-2-DIR
PURE-3-DIR
SEG
VPG
all-4-simplicial
balanced 2-interval
binary tree ∩ partial grid
bipartite ∩ boxicity 2
bipartite ∩ grid intersection
biplanar
bounded tolerance
boxicity 2
caterpillar arboricity <= 2
circle-polygon
clique graphs
co-bounded tolerance
co-comparability graphs of dimension d posets
co-comparability graphs of posets of interval dimension d
co-interval filament
co-interval mixed
co-perfectly orderable
co-sun-free
co-tolerance
comparability graphs of dimension 3 posets
comparability graphs of dimension 4 posets
comparability graphs of dimension d posets
comparability graphs of posets of interval dimension d
cubical
d-trapezoid
grid intersection
hamiltonian
harmonious
intersection graphs of parallelograms (squares)
interval filament
k-SEG
linear arboricity <= 2
max-tolerance
monopolar
outer-string
parallelepiped
partial 3d grid
partial grid
partial rectangle visibility
path orderable
perfectly orderable
polar
probe (2,2)-colorable
rectangle intersection
rectangle visibility
semi-square intersection
spider graph
string
sun-free
thickness <= 2
tolerance
tripartite
unit 2-interval
unit 2-track
unit 3-interval
unit 3-track
weak bisplit
weak rectangle visibility
back to top
coNP-complete
K
1,4
-free ∩ well covered
well covered
back to top
Open
(2,2)-interval
CIS
PI
almost CIS
alternation
bitolerance
cliquewidth 4
domination
hereditary clique-Helly ∩ self-clique
locally perfect
multitolerance
neighbourhood perfect
opposition
pairwise compatibility
partitionable
probe chordal bipartite
probe permutation
probe strongly chordal
proper tolerance
quasi-parity
strict quasi-parity
strongly perfect
superperfect
trapezoepiped
unit tolerance
visibility
back to top
Unknown to ISGCI
(1,2)-split
1-string
2-circular arc
2-circular track
2-connected ∩ linearly convex triangular grid graph
2-subdivision
2-subdivision ∩ planar
2-thin
3-DIR contact
3-circular track
4-regular ∩ hamiltonian
4-regular ∩ hamiltonian ∩ planar
5-regular ∩ hamiltonian
5-regular ∩ hamiltonian ∩ planar
(6,1)-chordal
(6,1)-even-chordal
(6,2)-chordal
B
0
-VPG ∩ chordal
B
0
-VPG ∩ strongly chordal
B
0
-VPG ∩ triangle-free
B
1
-VCPG
Birkhoff
(C
n+3
∪ K
1
,diamond,paw)-free
C
n+6
-free
C
n+7
-free
Gabriel
Gallai-perfect
Hamilton-connected
Helly circular arc ∩ self-clique
Helly subtree
Mycielski
PURE-k-DIR
Raspail
Urquhart
V-perfect
(W
4
,gem)-free ∩ short-chorded
β-perfect
cal P
3
-perfect
(
C
n+3
∪ K
1
,co-diamond,co-paw)-free
C
n+6
-free
C
n+7
-free
(n+4)-pan
-free
absorbantly perfect
almost median
(anti-hole,co-sun,hole)-free
(anti-hole,hole,sun)-free
basic perfect
bigeodetic
bip
*
bipartite ∩ unit grid intersection
bipartite ∪ co-bipartite ∪ co-line graphs of bipartite graphs ∪ double split ∪ line graphs of bipartite graphs
book thickness 2
bounded cutwidth
bounded degree
bounded degree ∩ bounded treewidth
bounded treewidth
boxicity 2 ∩ co-bipartite
chordal ∩ clique-chordal
chordal ∩ hamiltonian
chordal ∩ hamiltonian ∩ planar
chordal-perfect
circle-n-gon, fixed n
circle-trapezoid
circular convex bipartite
circular perfect
circular strip
circular trapezoid
(claw,odd anti-hole)-free ∩ tripartite
(claw,odd-hole)-free ∩ tripartite
claw-free ∩ odd anti-hole-free ∩ tripartite
claw-free ∩ odd-hole-free ∩ tripartite
claw-free ∩ upper domination perfect
clique-chordal
clique-perfect
clique-perfect ∩ triangle-free
co-2-subdivision
co-β-perfect
co-circular perfect
co-comparability ∩ tolerance
co-leaf power
comparability graphs of posets of interval dimension 2, height 3
containment graph of circles
cubic ∩ hamiltonian
cubic ∩ hamiltonian ∩ planar
diametral path
double split
even anti-hole-free
even-hole-free
even-signable
frame hereditary dominating pair
fully cycle extendable
graceful
grid graph
grid graph ∩ maximum degree 3
half
hamiltonian ∩ interval
hamiltonian ∩ planar
hamiltonian ∩ split
hereditary X-chordal
hereditary dominating pair
hereditary weakly modular
homothetic triangle contact
induced-hereditary pseudo-modular
interval enumerable
irredundance perfect
irredundance perfect with ir(G)=2
irredundance perfect with ir(G)<= 4
isometric-HH-free
k-DIR
leaf power
leaf power ∩ min leaf power
leaf power ∪ min leaf power
line graphs of planar cubic bipartite graphs
line perfect
linearly convex triangular grid graph
locally connected ∩ triangular grid graph
map
min leaf power
(n+4)-pan-free
normal
normal circular arc
odd co-sun-free
odd-sun-free
(p,q)-colorable
(p,q)-split
(p,q<=2)-colorable
perfectly contractile
polyhedral
power-chordal
preperfect
probe (1,2)-colorable
probe AT-free
probe Gallai
probe HHDS-free
probe Meyniel
probe co-comparability
probe comparability
(q,t)
relative neighbourhood graph
self-clique
short-chorded
skeletal
slender
slim
solid grid graph
solid triangular grid graph
strict B
1
-VCPG
strong domination perfect
strongly circular perfect
subhamiltonian
substar
subtree filament
subtree overlap
sun-free ∩ weakly chordal
thick tree
triad convex
triangular grid graph
unimodular
unit 2-circular arc
unit 2-circular track
unit 3-circular track
unit Helly circle
unit bar visibility
unit grid intersection
universally signable
upper domination perfect
upper irredundance perfect
walk regular
weak dominating pair
back to top
AltStyle
によって変換されたページ
(->オリジナル)
/
アドレス:
モード:
デフォルト
音声ブラウザ
ルビ付き
配色反転
文字拡大
モバイル