Terry McKee Home Terry A McKee

Department of Mathematics and Statistics Department of Mathematics and Statistics

College of Science and Mathematics College of Science and Mathematics

Wright State Home Wright State Home

 

Professor Emeritus, Mathematics and Statistics
Wright State University
3640 Colonel Glenn Highway
Dayton OH 45435-0001


messages 937.775.2785


fax 937.775.2081
 

long gold bar

  Topics in Intersection Graph Theory by TA McKee and FR McMorris  

Corrections and Updates to

Topics in Intersection Graph Theory by T.A. McKee and F.R. McMorris. [SIAM Monographs on Discrete Mathematics and Applications #2]
Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1999, vii+205 pp.

ISBN: 0-89871-430-3
QA 166.105.M34


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".

gold spacer bar

UPDATES TO THE BIBLIOGRAPHY

 

A. Brandstädt, V. B. Le & J. Spinrad (to appear).

Special graph classesA survey. Society for Industrial and Applied Mathematics, Philadelphia, 1999.

R. C. Brigham, F. R. McMorris & R. P. Vitray (to appear).

 

R. C. Brigham, J. R. Carrington & R. P. Vitray.

Bipartite graphs and absolute difference tolerances. Ars Combin. 54 (2000) 3-27.

J. S. Deogun & K. Gopalakrishnan (to appear).

Consecutive retrieval property---Revisited. Inform. Process. Lett. 69 (1999) 15-20.

E. M. Eschen, R. B. Hayward, J. P. Spinrad & R. Srigharan (to appear).

Weakly triangulated comparability graphs. SIAM J. Comput. 29 (1999) 378-386.

I.-J. Lin, T. A. McKee & D. B. West (to appear).

Leafage of chordal graphs. Discuss. Math. Graph Theory 18 (1998) 23-48.

J. R. Lundgren, P. A. McKenna, S. K. Merz & C. W. Rasmussen (to appear).

The $p$-competition graphs of symmetric digraphs and $p$-neighborhood graphs. J. Combin. Inform. System Sci. 22 (1997) 117-132.

N. V. R. Mahadev & T.-M. Wang (to appear).

On uniquely intersectable graphs. Discrete Math. 207 (1999) 149-159.

T. A. McKee (to appear(a)).

An inequality characterizing chordal graphs. Ars Combin. 51 (1999) 121-127.

T. A. McKee (to appear(b)).

Strong clique trees, neighborhood trees, and strongly chordal graphs. J. Graph Theory 33 (2000) 151-160.

F. R. McMorris, C. Wang & P. Zhang (to appear).

On probe interval graphs. Discrete Appl. Math. 88 (1998) 315-324.

F. R. McMorris & C. Wang (to appear).

Sphere-of-attraction graphs. Congr. Numer. 142 (2000) 149-160.

T. B. Moorhouse & D. G. Corneil (to appear(b)).

Completeness for intersection classes. Discrete Math. 190 (1998) 277-286.

B. Pondĕlíček (to appear).
Chordal intersection graphs of bands. Czechoslovak Math. J. 49 (1999) 225-232.
E. Prisner (to appear).

Intersection multigraphs of uniform hypergraphs. Graphs Combin. 14 (1998) 363-375.

L. Sheng, C. Wang & P. Zhang (to appear).

Tagged probe interval graphs. J. Comb. Optim. 5 (2001) 133-142.

long gold bar
Terry A McKee home page
Course information  | Brief vita
Topics in Intersection Graph Theory
corrections/updates; ordering information and review
Intersection graphs | Graph duality  | Graph meta-theory | Miscellaneous graph theory | Mathematical logic | Truly miscellaneous

long gold bar


Email me your comments, questions and suggestions concerning this site. (sjm)

Official WSU disclaimer.