|
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
"is a minimal vertex weak separator of
$G$ ..." with "is a minimal vertex
weak separator of a graph $G$ having clique
tree $T$ ...".
Section 3.1 — Page 48, the
end of the proof of Theorem 3.3. The following
should fix 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.) Let me know if you'd like me to
e-mail you a .dvi or .ps version.
Conversely,
suppose $G$ is a minimum-order chordal graph
that is not an interval graph and that has no
asteroidal triple (arguing toward a contradiction).
Suppose $T$ is a clique tree of $G$ that has
a minimum number $(\ge 3)$ of leaves. Suppose
$Q_1$, $Q_2$, and $Q_3$ are three different
leaves of $T$ and let, respectively, $Q'_1$,
$Q'_2$, and $Q'_3$ (not necessarily distinct)
be their unique neighbors in $T$.
For
each $i = 1,2,3$, choose $v_i \in V(Q_i)$ such
that $v_i \not\in V(Q'_i)$. By assumption, $\{v_1,v_2,v_3\}$
is not an asteroidal triple of $G$, and we can
further assume, without loss of generality,
that every path in $G$ connecting $v_1$ and
$v_3$ contains a neighbor of $v_2$. Not every
edge of the path $T(Q_1,Q_3)$ in $T$ can contain
a non-neighbor of $v_2$, since otherwise those
non-neighbors could be used to induce a $v_1$-to-$v_3$
path in $G$ that contained no neighbor of $v_2$.
Therefore, the path $T(Q_1,Q_3)$ would contain
some edge $Q^*Q^{**}$ with $Q^* \cap Q^{**}$
consisting entirely of neighbors of $v_2$, making
$Q^* \cap Q^{**} \subseteq Q_2 \cap Q'_2$.
Without
loss of generality, suppose $Q^*$ is closer
to both $Q_1$ and $Q_2$ in $T$ than is $Q^{**}$.
Then replacing edge $Q^*Q^{**}$ with a new edge
$Q^{**}Q_2$ would create a clique tree $T^*$
for $G$ in which $Q_2$ is not a leaf. If $Q^*$
is also not a leaf of $T^*$, then $T^*$ would
have one fewer leaf than $T$, contradicting
the choice of $T$. Therefore we can assume that
$Q^*$ is a leaf of $T^*$. Then $Q^*$ will also
be a leaf of the tree $T^-$ obtained from $T$
by deleting all the vertices of $T(Q^{**},Q_3)$;
note that $T^-$ is a clique tree for the induced
subgraph $G^-$ of $G$ obtained by deleting all
the vertices that only occur in vertices of
$T(Q^{**},Q_3)$. If $G^-$ is a chordal graph
smaller than $G$ that is not an interval graph,
then the choice of $G$ would ensure that $G^-$
has an asteroidal triple, which would contradict
that $G$ has no asteroidal triple. Therefore
we can assume that $G^-$ is an interval graph.
Observe that all the vertices of $T^-(Q^*,Q_2)$
will have to constitute a subpath of any clique
path for $G^-$. Since all the vertices of $G^-$
that are not in $Q^* \cap Q_2$ occur in some
single vertex from $T^-(Q^*,Q_2)$, some clique
path of $G^-$ would have to have an endpoint
$\widehat{Q}$ from among the vertices of $T^-(Q^*,Q_2$).
But then that clique path of $G^-$, together
with an new edge $\widehat{Q}Q^{**}$ and the
tree $T(Q^{**},Q_3)$, would produce a clique
tree for $G$ with one fewer leaf than $T$, again
contradicting the original choice of $T$. \hfill$\Box$
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
|
