List of Misprints, Corrections and Updates
Table of Contents
Chapter 1: Basic Concepts,
Chapter 2: Perfection, Generalized Perfection, and Related Concepts,
Chapter 3: Cycles, Chords, and Bridges,
Chapter 4: Models and Interactions,
Chapter 5: Vertex and Edge Orderings,
Chapter 6: Posets,
Chapter 7: Forbidden Subgraphs,
Chapter 8: Hypergraphs and Graphs,
Chapter 9: Matrices and Polyhedra,
Chapter 10: Distance Properties,
Chapter 11: Algebraic Compositions and Recursive Definitions,
Chapter 12: Decompositions and Cutsets,
Chapter 13: Threshold Graphs and Related Concepts,
Chapter 14: The Strong Perfect Graph Conjecture,
Appendix A: Recognition,
Appendix B: Containment Relationships,
Acknowledgements.
| Page |
Line(s) |
Text |
Replaced by |
| 16 |
-10 |
[1025] |
[1021] |
| 16 |
-11 |
[935] |
[928] |
| 17 |
8 |
[628, ..., 635] |
[627, ..., 634] |
Table of Contents
Chapter 2: Perfection, Generalized Perfection, and Related Concepts
| Page |
Line(s) |
Text |
Replaced by |
| 22 |
14 |
minimal-dominating |
minimal dominating |
| 24 |
8 |
Strong Perfect Graph Conjecture |
Strong Perfect Graph Theorem |
| 25 |
8 |
[905] |
[901] |
| 26 |
1, 3 |
[222] |
[220] |
| 26 |
17, 19 |
[210] |
[208] |
| 27 |
-5, -6 |
[565] |
[563] |
| 29 |
-3 |
[306] |
[304] |
| 30 |
7 |
[98] |
remove [98] |
| 30 |
12 |
[98] |
[97] |
| 32 |
4 |
[540] |
[538] |
| 33 |
-13 |
[964] |
[957] |
Table of Contents
Chapter 3: Cycles, Chords, and Bridges
| Page |
Line(s) |
Text |
Replaced by |
| 43 |
13 |
[374] |
[372] |
| 44 |
14 |
Appendix A |
Appendix B |
Table of Contents
Chapter 4: Models and Interactions
| Page |
Line(s) |
Text |
Replaced by |
| 55 |
-15 |
[1037] |
[1033] |
| 56 |
12 |
Theorem 7.1.11 |
Theorem 7.1.10 |
Table of Contents
Chapter 5: Vertex and Edge Orderings
| Page |
Line(s) |
Text |
Replaced by/Remarks |
| 70 |
8/9 |
Sentence after Definition 5.2.1 |
whole sentence must be removed |
| 70 |
15 |
an |
a |
| 72 |
5-9 |
Quasi triangulated |
This concept has been introcuced by V.Voloshin in [6] |
| 78 |
-13 |
an |
a |
| 82 |
18 |
O(m^3\log^2n) |
P |
Table of Contents
| Page |
Line(s) |
Text |
Replaced by |
| 101 |
-6 |
[717] |
[716] |
| |
|
[494] |
[492] |
| |
-7 |
[475] |
[473] |
Table of Contents
| Page |
Line(s) |
Text |
Replaced by |
| 111 |
12 |
[907] |
[906] |
| |
15 |
[538] |
[536] |
Table of Contents
Chapter 8: Hypergraphs and Graphs
Table of Contents
Chapter 9: Matrices and Polyhedra
Table of Contents
| Page |
Line(s) |
Text |
Remarks |
| 164 |
15 |
An open question |
The answer is yes ([4]) |
Table of Contents
Chapter 11: Algebraic Compositions and Recursive Definitions
| Page |
Line(s) |
Text |
Replaced by |
| 169 |
2 |
[25] |
[26] |
| 176 |
8 |
subgraph (in Theorem 11.3.3) |
induced subgraph |
| 183 |
-16 |
Whitesides's |
Whitesides' |
Table of Contents
Chapter 12: Decompositions and Cutsets
Table of Contents
Chapter 13: Threshold Graphs and Related Concepts
| Page |
Line(s) |
Text |
Replaced by |
| 203 |
-1 |
k |
m |
| 204 |
1 |
k |
m |
| |
3 |
k |
m |
| |
8 |
\lfloor m/2 -1 \rfloor |
\lfoor m/2 \rfloor -1 |
Table of Contents
Chapter 14: The Strong Perfect Graph Conjecture
| Page |
Line(s) |
Text |
Replaced by |
| 207 |
-9 |
Strong Perfect Graph Conjecture |
Strong Perfect Graph Theorem |
| 211 |
-6 |
[222] |
remove [222] |
| |
-7 |
in |
in [222] |
| 219 |
11 |
[896] |
[892] |
| 220 |
-10 |
tile |
lite |
Table of Contents
| Page |
Graph class |
Time bound/Reference |
Replaced by |
| 223 |
bipolarizable |
O(n^{\alpha+1}) |
O(n m) ([10]) |
| 224 |
AT-free |
O(n^{3}) |
O(n^{2.83}) ([7]) |
| |
circular arc |
O(n^{2}) |
LIN ([8]) |
|
cograph |
[255] |
[256] |
| 225 |
maxibrittle |
P |
O(n^{3.376}) ([14]) |
| |
median |
O(\min m\sqrt{n}, n^{1.5}\log n) |
O(n^{1.41}) ([3]) |
| 226 |
$P_4$-comparability |
O(n^2m) |
O(n m) ([9]) |
| |
$P_4$-indifference |
O(n^2m) |
LIN ([2], [5]) |
| |
$P_4$-simplicial |
O(m^3\log^2 m) |
O(n m) ([10]) |
| |
perfect |
??? |
P ([11], [12], [13]) |
| |
strongly chordal |
[373] |
[372] |
| |
superbrittle |
P |
LIN ([1]) |
| 227 |
Welsh-Powell opposition |
O(n^4) |
O(n^3) ([14]) |
Table of Contents
Appendix B: Containment Relationships
| Page |
Graph class |
Contained in |
| 243 |
outerplanar |
2-interval ([959]) |
| 248 |
tree |
outerplanar |
Table of Contents
References
[1] A. Brandstädt, V.B. Le, Split-perfect graphs:
Characterizations and algorithmic use, to appear in SIAM J. Discrete Math.
[2] M. Habib, C. Paul, L. Viennot, Linear time recognition
of P4-indifference graphs, DMTCS
4 (2001) 173-178
[3] W. Imrich, S. Klavzar, Product Graphs,
Wiley, 2000
[4] E. Prisner, A note on powers and proper circular-arc
graphs, preprint, 1999
[5] R. Rizzi, On the recognition of P4-indifferent graphs,
Discrete Math. 239 (2001) 161-169
[6] V.I. Voloshin, Quasi-triangulated graphs,
Preprint No 5569-81, Kishinev State U, Kishinev, 1981 (in Russian)
[7] D. Kratsch, J. Spinrad, Between O(nm) and O(n^\alpha),
manuscript, 2001
[8] R. McConnell, Linear time recognition algorithm for circular arc graphs,
Algorithmica 37 (2003) 93-147
[9] S.D. Nikolopoulos, L. Palios, On the recognition of
P4-comparability graphs, WG2002, LNCS 2573 (2002) 355-366
[10] S.D. Nikolopoulos, L. Palios, Recognizing bipolarizable and
P4-simplicial graphs, WG2003, LNCS 2880 (2003) 358-369
[11] M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic, Cleaning for Bergeness, manuscript 2003
[12] M. Chudnovsky, P. Seymour, Recognizing Berge graphs, manuscript 2003
[13] G. Cornuejols, X. Liu, K. Vuskovic, A polynomial algorithm for recognizing perfect graphs, manuscript 2003
[14] E.M. Eschen, J.L. Johnson, J.P. Spinrad, R. Sritharan, Recognition of some perfectly orderable graph classes, Discrete Applied Math. 128 (2003) 355-373
We thank the following people for their kind hints and remarks:
Gordon F. Royle,
Ryan B. Hayward,
Erich Prisner,
Vitaly Voloshin,
Pascal Ochem
Back to Graph Classes: A Survey
{ab,le}@informatik.uni-rostock.de, spin@vusa.vanderbilt.edu