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 west@math.uiuc.edu. 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 "knn-k-1"
• 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 "-|S2|2"
• 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 (Reza Zamani)
• 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 (Jennifer Vandenbussche)
• 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 "|\partial C|"
• 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 described
• p406, after Def9.3.26: "edge-disjoint subgraphs" should be "edge-disjoint cycles"
• p406, Thm9.3.27: "this is a collection of" should be "the boundaries are"
• 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" (Mohit Kumbhat)

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" (Reza Zamani)
• `
• 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" (Reza Zamani)
• 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" (Jennifer Vandenbussche)
• 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 congruence"
• p371, Alg9.1.9: "finitely choices" should be "finitely many choices"
• p407, start of section: "k+1-flow. so" should be "(k+1)-flow, so"
• p470, last line: "Chromatic polynomials such graphs" should be "Chromatic polynomials of such graphs"