``Structure of Graphs (TAC: Vol. II)'' - Typos
This page lists the errors that have been discovered in the Spring 2005
pre-publication version of Structure of Graphs, by Douglas B. West
(Volume II of The Art of Combinatorics).
This page is of interest only to the few persons having a copy of this
draft, such as the students in my course and possibly reviewers.
Please send any additional contributions to email@example.com.
Contributors noted in parentheses.
Category 1: Notational typos and other Mathematical Corrections
- p36, Thm6.1.5: "solid edges" and "dashed edges" should be "bold edges"
and "solid edges" (Reza Zamani)
- p57, Exm6.1.57: This example shows that Conjecture 6.1.57 is sharp,
not that Theorem 6.1.56 is sharp
- p59, Exr6.1.22: it should also be required that G has more than
k vertices, in case G is complete
- p62, Exr6.1.49: "knn-k-1" should be
- p84, Thm6.2.23: "ak+1" should be
"1+maxiai" (Reza Zamani)p94-95, Def6.3.10-Thm6.3.11: The relation in the definition of
F-chain should be induced subgraph, and the computation to prove the
Counting Theorem should then use the induced subgraph version of
Kelly's Lemma, where s*QG is the number of
induced subgraphs of G isomorphic to Q.
- p101, Thm6.3.21: "B" should be "Q" (twice), and
"1-vertex" should be "one vertex"
- p102, Cor6.3.24: "E(G)" should be "e(G)", and "the copies"
should be "copies"
- p105, Cor6.3.33: delete "is this large"
- p105, Thm6.3.32: all six instances of "Q" should be "G".
The "=1" in the final line should be dropped (Reza Zamani)
- p111, Def6.4.1: "is a map" should be "is an injective function"
- p150, Lem7.1.44: in the displayed equation,
"+|S2|2" should be
- p151, Lem7.1.44: The weak containment symbols relating source sets should
be strict containment; also
also "Sj" should be "Sj".
In the last part of the proof, the indices i and j refer
to the same thing.
- p152, Thm7.1.45: "that avoid f" should be "that avoid e"
- p157, Def7.1.55: the 2k vertices should be required to be distinct
- p176, Lem7.2.19: "separates b" should be "separates z",
and "Let R be" should be "Let W be"
- p161, Exr7.1.30: The claim holds when F is nonempty
- p170, after Exm7.2.12: "a vertex split. This stimulates" should be
"a disjoint 3-split. This stimulates" (Reza Zamani)
- p179, revised proof of Gyori-Lovasz: "y\in Fi"
should be "y\in V(Fi)". Also,
"since \partial(Cj) contains only vertices not in C"
should be "since y was chosen from \partial(C)" (Reza Zamani)
- p188, Exr7.2.33: close brace missing
- p198, Def7.3.9: this definition of the k-closure always yields the
complete graph. The proper statement is to iteratively add edges joining
nonadjacent vertices with degree-sum at least k
- p203, after Def7.3.22: "\partial C" should be
- p260, picture: the labels "v1",
"v2", and "v3" on the second graph
should be deleted
- p290, Lem8.2.24: "xy,uv" should be "xu,yv"
- p301, bottom: the independence ratio guaranteed by Albertson is
2/9, not 4/9
- p303, Thm8.2.39: "3-degenerate" should be "2-degenerate".
Condition (c) is not needed for the proof, the construction simply produces
a representation with this additional property.
- p305, Thm8.2.41: The sentence about cycles allows us to assume that G
has maximum degree at least 3, not minimum degree at least 3. Several
references to the edge v0v1 should be to
v0vk. "each new edge" should be "each new vertex"
"left of f(vi1-1)" should be
"right of f(vi1-1)".
- p374, Thm9.1.14: The statement is not correct, since K3,3
has no K5-minor but is not contained in the family
- p406, after Def9.3.26: "edge-disjoint subgraphs" should be "edge-disjoint
- p406, Thm9.3.27: "this is a collection of" should be "the boundaries
- p411, Thm9.3.38: In the first line of the proof,
"(D,f)" should be "(D,f')"
- p412, Lem9.3.42: The desired even subgraph S may be chosen to be
a disjoint union of necklaces, not a single necklace
- p424, middle: "minimum Eulerian weight has total weight 20" should be
"minimum Eulerian 1,2-weight has total weight 20"
- p438, Exr9.3.32: same correction as for p424
- p444, Lem10.1.10, last line: "eigenvector" should be "eigenvalue"
Category 2: Other Changes, Comments and Corrections of Note
- p148, Cor7.1.38: It is easy to avoid Menger's Theorem, since A => C => B
is quite easy and B => A is Edmonds' Branching Theorem.
A new item is being added (Seymour ) that uses the Branching Theorem
directly and simply to obtain the local edge digraph version of Menger's
Theorem, from which all other versions follow.
- p162-3: Exr7.1.40 repeats 7.1.35, and Exr7.1.53 repeats 7.1.36.
- p332, Thm8.3.27: Bienstock and Dean published two papers on t-linear
crossing numbers; the correct date for this theorem is 1992.
- p436, Exr9.3.15: repeats 9.3.10.
- p436, Exr9.3.17: editing glitch; this is the beginning of 9.3.18 plus the
end of 9.3.16.
Category 3: Minor Changes, Typos, and Clarifications
- p59, Exr6.1.18: "or an edge" should be "or two adjacent vertices"
- p73, before Def6.2.5: "In an algorithmic" should be "An algorithmic"
- p78, Lem6.2.15: "i row" should be "ith row"
- p97, Def6.3.14: add missing close parenthesis
- p99, Thm6.3.19: "Such a arm" should be "Such an arm" (Reza Zamani)
- p108, top: "is determine" should be "is determined"
- p122, top: "Nesetril-Rodl dimension of" should be
"Nesetril-Rodl dimension or" should be
- p138, Def7.1.21: "a such a" should be "such a" (Reza Zamani)
- p146, Thm7.1.35: "cap[S,T]" should be "cap(S,T)".
In the line after the proof, "consider" should be "considers" (Reza Zamani)
- p149, top: "via a algorithm" should be "via an algorithm"
- p152, Thm7.1.45: "of of" should be "of" (Reza Zamani) (a revision of this
proof was distributed in class)
- p157, Thm7.1.56: "with edges cuts . . . leave" should be "having an edge
cut . . . leaves" (Reza Zamani)
- p162, Exr7.1.36: "set S set" should be "set S"
- p165, Thm7.2.1: "correspondence to" should be "correspond to"
- p169, after Thm7.2.8: "Thomassen's Contraction Lemma" should be
"the Contraction Lemma" (Jennifer Vandenbussche)
- p169, Rem7.2.9: "does generalizes" should be "does generalize"
- p170, Exm7.2.12: "by apply" should be "by applying" (Reza Zamani)
- p170, before Lem7.2.13: "show how apply it" should be "show how to apply
it" (Jennifer Vandenbussche)
- p256, Rem8.1.52: "vertiex" should be "vertex"
- p259, Thm8.1.59: "forms a Ti" should be
"forms a tree Ti"
- p360, bottom: "only the congruence" should be "only when the
- p371, Alg9.1.9: "finitely choices" should be "finitely many choices"
- p407, start of section: "k+1-flow. so" should be
- p470, last line: "Chromatic polynomials such graphs" should be
"Chromatic polynomials of such graphs"