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