CORRECTIONS
Section 2.1 Pages 22-23,
Proof of Theorem 2.3.
The following is a simplified proof.
Let me know if you'd like me to e-mail you
a .dvi or .ps version.
{\bf
Proof.}If some maximum spanning tree of $K^w(G)$
is a clique tree for $G$, then by definition
$G$ is a connected subtree graph.
Conversely,
suppose $G$ is a connected subtree graph with
clique tree $T$.
Notice that, by the proof of Lemma 2.2, the
left side of (2.1) is less than or equal to
the right side for all spanning trees of K(G)
(with equality holding if and only if the spanning
tree is a clique tree). Since the first two
terms in (2.1) are fixed and the last term is
being maximized, and since equality holds in
(2.1) for the clique tree $T$, equality must
hold for every maximum spanning tree of $K^w(G)$.
Then Lemma 2.2 implies that every maximum spanning
tree of $K^w(G)$ is a clique tree for $G$. \hfill$\Box$
Section
2.2 Page 24, Exercise 2.9, second
paragraph; replace with the following:
Show that $S$ is a minimal vertex weak separator of a graph $G$ with a clique tree $T$ such that $S$ is not a proper subset of another minimal vertex separator of $G$ if and only if there exists a dominated chord $Q_iQ_j$ of $T$ such that $S = Q_i \cap \Q_j$.
Section 3.1 Page 48, the
end of the proof of Theorem 3.3. There is
a mistake in the if direction ("Conversely,
...") of the proof of the Lekerkerker-Boland
Theorem.
(As noticed by Pavol Hell, Q* might become
a leaf.) A correct, clique-tree based proof is
in the paper Asteroids in rooted and
directed path graphs, by K. Cameron, C. T. Hoàng,
and B. Lévêque, currently posted online at
arXiv:0812.2734v2.
Section
3.3 Page 55, Exercise 3.12:
replace
"contains no cycle ..."
with "contains no induced cycle ...".
Section 3.3 Pages 55-56,
the end of the proof of Theorem 3.8. The following
should fix a mistake in the proof. Let me
know if you'd like me to e-mail you a .dvi or
.ps version.
{\bf
Proof.} As we observed, the implication
one way is immediate. To prove the converse,
suppose $G$ is a proper interval graph. Arguing
inductively, suppose that, for every proper
subgraph $G'$ of $G$, every proper path representation
of $G'$ can be made into a unit path representation
of $G'$ by simply inserting additional vertices
into the path. Suppose $P$ is a proper path
representation for $G$ and pick a simplicial
$v \in V(G)$ that occurs in an end vertex of
$P$. Obtain a proper path representation $P^+$
from $P$ by inserting additional vertices into
$P$ so that removing all occurrences of $v$
from $P^+$ would leave a unit path representation
of the subgraph induced by $V(G)\backslash\{v\}$.
Since $v$ is simplicial, we can assume that
$v$ still occurs in an end vertex of $P^+$.
Let $k = |V(P^+_w)|$ for each $w \not= v$. Then
$k \ge |V(P^+_v)|$, since $P^+$ is still a proper
path representation, and so adding $k - |V(P^+_v)|$
new vertices, each equal to $\{v\}$, to the
end vertex that contains $v$ will produce a
unit path representation of $G$. \hfill $\Box$\\
Section 4.1 Page 68, Figure
4.2:
insert
an edge in $G$ between $v_1$ and $v_3$.
Section 5.1 Page 81, Figure
5.3:
insert
an edge between $D_m$ and $D_{m-2}$.
Section 6.3 Page 106,
Figure 6.8:
insert
an edge between $D_m$ and $D_{m-2}$.
Section
7.3 Page 123, Theorem 7.21:
replace
"A graph is ..." with "A bipartite graph is
...".
Section
7.12 Page 146, lines 4 and 5 from
the bottom:
"strongly
balanced" should be "totally balanced."
Bibliography
Page 154:
replace
"R. C. Brigham, F. R. McMorris & R.
P. Vitray (to appear)" with "R.
C. Brigham, J. R. Carrington & R. P. Vitray
(to appear)" (the rest of the citation
and the references in the text are correct).
Bibliography
Page 168:
replace
"F. Harary, M. S. Jacobson, M. J. Lipman
& F. R. McMorris (to appear)" with
"M. S. Jacobson, M. J. Lipman & F.
R. McMorris (to appear)" (which appears
correctly on page 171; the references in the
text are correct).
Bibliography
Page 173:
replace
"L. L. Kelleher & M. B. Cozzens (1990).
Coloring interval graphs with First-Fit" with
"M. B. Cozzens & L. L. Kelleher (1990).
Dominating cliques in graphs" (the rest of the citation
and the references in the
text are correct).
Bibliography
Page 256:
replace
"[139] A. Bouchet (1994). Circle graph obstructions.
Discrete Math. 60, 107--144. Cited in \S7.4
" with
"[139] A. Bouchet (1994). Circle graph obstructions.
J. Combin. Theory B 60, 107--144. Cited in \S7.4".
UPDATES TO THE BIBLIOGRAPHY
|